Question

Which of the following sorting algorithms has the worst-case time complexity of O($n^2$)?

• A. Merge Sort
• B. Quick Sort
• C. Bubble Sort
• D. Heap Sort

Hint:

To understand sorting complexities:
- Learn worst-case scenarios: Bubble Sort (O($n^2$)), Merge/Heap Sort (O(n log n)).
- Quick Sort’s O($n^2$) is avoidable with good pivot selection.
- Practice with small arrays to observe behavior.

Answer 1

The Correct Option is C

To determine which sorting algorithm has a worst-case time complexity of O($n^2$), we need to evaluate the time complexity of each algorithm in its worst-case scenario.
Step 1: Understand Time Complexity
The worst-case time complexity indicates the maximum time an algorithm takes for any input of size n.
O($n^24$) means the time grows quadratically with the input size, typically seen in algorithms with nested loops.
Step 2: Analyze Option A - Merge Sort
Merge Sort uses a divide-and-conquer approach, splitting the array into halves and merging them.
Its worst-case time complexity is O(n log n) due to the merging process.
Thus, option A is incorrect.
Step 3: Analyze Option B - Quick Sort
Quick Sort also uses a divide-and-conquer strategy, partitioning the array around a pivot.
Its average-case time complexity is O(n log n), but the worst case (e.g., already sorted array with a bad pivot) is O($n^2$).
However, the question asks for the algorithm where O($n^2$) is the standard worst-case, not an exceptional case.
Thus, option B is not the best answer here.
Step 4: Analyze Option C - Bubble Sort
Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.
In the worst case (e.g., reverse-sorted array), it requires n-1 passes with up to n-1 comparisons each, leading to O($n^2$) time complexity.
This is the standard worst-case for Bubble Sort.
Thus, option C is correct.
Step 5: Analyze Option D - Heap Sort
Heap Sort builds a max-heap and repeatedly extracts the maximum element, with a time complexity of O(n log n) in all cases (best, average, and worst).
Thus, option D is incorrect.
Step 6: Why the Other Options Are Incorrect
- Option A (Merge Sort): Always O(n log n), better than O($n^2$).
- Option B (Quick Sort): Worst case is O($n^2$) but not its defining characteristic; it’s typically optimized to avoid this.
- Option D (Heap Sort): Consistently O(n log n), never O($n^2$).
Bubble Sort’s O($n^2$) is its standard worst-case behavior.
Step 7: Key Insight
While Quick Sort can reach O($n^2$) in rare cases, Bubble Sort is inherently O($n^2$) in its worst case due to its simple, unoptimized comparison approach.