What is the worst case time complexity of bubble sort?
2021
What is the worst case time complexity of bubble sort?
- A.
O(x)
- B.
O(log2 x)
- C.
O(x2)
- D.
O(x log2 x)
Attempted by 519 students.
Show answer & explanation
Correct answer: C
In the worst case (when the array is sorted in reverse order), Bubble Sort performs: x−1 comparisons in the first pass , x−2 in the second pass , and so on.
Total comparisons:
(x−1)+(x−2)+⋯+1 = (x(x−1))/2
Thus, the growth rate is quadratic.