Which one of the following is the recurrence equation for the worst case time…
2015
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting \(n\) ( ≥ 2) numbers? In the recurrence equations given in the options below, \(c\) is a constant.
- A.
\(𝑇(𝑛) = 2 \ 𝑇(𝑛/2) + 𝑐n\) - B.
\(𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑇(1) + 𝑐n\) - C.
\( 𝑇(𝑛) = 2𝑇(𝑛 − 1) + cn\) - D.
\(𝑇(𝑛) = 𝑇(𝑛/2) + 𝑐n\)
Attempted by 429 students.
Show answer & explanation
Correct answer: B
Key insight: the worst case occurs when the pivot always ends up as the smallest or largest element, producing partitions of sizes n−1 and 0.
Partitioning step costs Θ(n) work, represented by c n.
One recursive call sorts n−1 elements, giving T(n−1). The other subproblem is size 0 or 1 and contributes a constant, T(1).
Therefore the worst-case recurrence (for n ≥ 2) is T(n) = T(n−1) + T(1) + c n. Summing the work over recursive levels yields Θ(n^2) overall.
A video solution is available for this question — log in and enroll to watch it.