- 2073 Bhadra · 2 marks
Best, average, worst case of sorts
Short answer
Bubble sort: O(n) best (with flag), O(n^2) average/worst. Insertion sort: O(n) best, O(n^2) average/worst. Merge sort: O(n log n) all cases. Selection sort: O(n^2) all cases.
Provide best case, average case and worst case for the following algorithms in Big-Oh: bubble sort, insertion sort, merge sort and selection sort.
| Algorithm | Best case | Average case | Worst case |
|---|---|---|---|
| Bubble sort | O(n) (with swap-flag, already sorted) | O(n²) | O(n²) |
| Insertion sort | O(n) (already sorted) | O(n²) | O(n²) (reverse order) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) |
| Selection sort | O(n²) | O(n²) | O(n²) |
Without the early-exit flag, bubble sort is O(n²) even in the best case. Selection sort always scans the full unsorted part, so it never improves. Merge sort halves the list each time (log n levels) and merges in O(n) per level.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Big-Oh significance and limitation · Data Structure and Algorithm, chapter 9
- Merge sort on 85, 76, 46, 92, ... · Data Structure and Algorithm, chapter 7
- Merge sort algorithm and trace · Data Structure and Algorithm, chapter 7
- Merge and radix sort on 142, 523, ... · Data Structure and Algorithm, chapter 7
- Merge sort on 47, 27, 56, 23, ... · Data Structure and Algorithm, chapter 7
- Heap tree insertion and heap sort · Data Structure and Algorithm, chapter 7
- Correct program: case array and average · Computer Programming, chapter 3
- Case study: feasibility, drawbacks, convincing · Instrumentation II, chapter 10
- Sort employee structures by salary · Computer Programming, chapter 8 · asked 2×
- Microprocessors in instrumentation systems (case study) · Instrumentation II, chapter 1