QuickSort
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.
T(n) = 2T(n/2) + cn  
T(n) = T(n – 1) + T(1) + cn  
T(n) = 2T(n – 1) + cn  
T(n) = T(n/2) + cn

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 subblock, one element (pivot) in the correct place and sub block of size n1.
Hence recurrence relation T(n) = T(n  1) + T(1) + cn.
Hence recurrence relation T(n) = T(n  1) + T(1) + cn.
There is 1 question to complete.