Which sorting algorithm has a worst-case time complexity of O(n²)?
2023
Which sorting algorithm has a worst-case time complexity of O(n²)?
- A.
Merge Sort
- B.
Radix Sort
- C.
Bubble Sort
- D.
Heap Sort
- E.
None of the above
Attempted by 16 students.
Show answer & explanation
Correct answer: C
Concept
The worst-case time complexity describes the maximum number of basic operations an algorithm performs as the input size n grows, expressed in Big-O notation. Comparison-based sorts are bounded below by O(n log n) in the best achievable worst case, but simple nested-loop sorts that compare and swap adjacent or selected elements run in O(n2) time because they perform on the order of n passes, each doing up to n work. In exam usage, asking which algorithm “has worst-case complexity O(n2)” means which one has a tight (Θ) quadratic worst case; an algorithm that stays O(n log n) or linear in the worst case does not qualify.
Application
Compare the worst-case bounds of each candidate:
Algorithm | Worst-case time | Why |
|---|---|---|
Merge Sort | O(n log n) | Divides the array into halves (log n levels) and merges in linear time per level. |
Radix Sort | O(d(n+b)) | Non-comparison digit-by-digit sort; linear in n for fixed digit count d and base b. |
Bubble Sort | O(n^2) | Two nested loops; up to n passes each scanning ~n elements, swapping adjacent items. |
Heap Sort | O(n log n) | Builds a heap and extracts the max n times, each extraction costing O(log n). |
Only Bubble Sort runs in O(n2) in the worst case, driven by its two nested loops over the array.
Cross-check
Merge Sort, Heap Sort (both O(n log n)) and Radix Sort (linear) are all asymptotically faster than O(n2), so none of them fits the requirement. Because a matching option exists, “None of the above” does not apply. Hence the answer is Bubble Sort.