Question

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n($\ge$2) numbers? In the recurrence equations given in the options below, c is a constant.

• A. T(n) = T (n -1) + T(1) + cn
• B. T(n) = 2T (n -1) + cn
• C. T(n) = 2T(n/2) + cn
• D. T(n) = 2T (n -1) + cn

Answer 1

The correct option is A T(n) = T (n -1) + T(1) + cn

In worst case the pivot element position may be either first or last . In that case the elements are always divided in 1 : (n - 1) proportion.
The recurrence relation for such a proportional division would be
T(n) = T(1) + T(n -1 ) + 0(n) = 0($n^2$)
(a) T(n) = 2T (n/2) + cn = 0( n log n)
(b) T(n) = T(n -1) + T(1) + cn = 0($n^2$)
(c) T(n) = 2T(n - 1) + cn = 0($n^2$)
(d) T(n) = T(n/2) + cn = 0(n)