Quick-Sort

Question 1

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
T(n) = 2T(n/2) + cn
B
T(n) = T(n – 1) + T(1) + cn
C
T(n) = 2T(n – 1) + cn
D
T(n) = T(n/2) + cn
AlgorithmsQuick-SortGATE 2015 [Set-1]Video-Explanation
Question 1 Explanation: 
When the pivot is the smallest (or largest) element at partitioning on a block of size n the result yields one empty sub-block, one element (pivot) in the correct place and sub block of size n-1.
Hence recurrence relation T(n) = T(n - 1) + T(1) + cn.
There is 1 question to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access