What is the worst-case running time of the Quick Sort algorithm?
2021
What is the worst-case running time of the Quick Sort algorithm?
Answer: B. Θ(n²) — Instead of dividing the array roughly in half, each partition leaves one subarray of size n−1 : T(n)=T(n−1)+(n−1) Solving this recurrence gives:…
- A.
Θ(n)
- B.
Θ(n²)
- C.
Θ(n log n)
- D.
Θ(n log² n)
Attempted by 1097 students.
Show answer & explanation
Correct answer: B
Instead of dividing the array roughly in half, each partition leaves one subarray of size n−1 :
T(n)=T(n−1)+(n−1)
Solving this recurrence gives:
1+2+3+⋯+(n−1)=O(n2)
Loading lesson…