Question

what’s T(n) of the QuickSort algorithm in (1) the best case, (2) the worst
case and (3) the case where the partition() algorithm always splits the input
array with a 40:60 ratio (i.e., 40% of data goes in one partition and the
remaining 60% the other)?
algorithm quicksort(A, lo, hi)
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p - 1 )
quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi)
pivot := A[hi]
i := lo - 1
for j := lo to hi - 1 do
if A[j] < pivot then
i := i + 1
swap A[i] with A[j]
if A[hi] < A[i + 1] then
swap A[i + 1] with A[hi]
return i + 1

Answer 1

Answer :

BEST CASE : T(n) = 2T(n/2) + n

Explanation : Best CASE Occurs when the PIVOT is taken in the Middle of the array and we divide the array into two halves equally ..So we have two halves of n/2 and n/2 hence we write T(n/2) + T(n/2) which becomes 2T(n/2).
The term n comes as addition because at every step we partition the array and Paritioning takes n time
Hence combining both of them we get 2T(n/2) + n

Worst Case : T(n) = T(n - 1) + n

Explanation : WORST CASE Occurs when the INPUT IS SORTED and my Array will divide in 1 and n-1 elements
The term n comes as addition because at every step we partition the array and Paritioning takes n time
Hence combining both of them we get T(n-1) + n

3) Case where partition is 40: 60 that means 2n/5 and 3n/5

=> T(n) = T(2n/5) + T(3n/5) + n

Explanation: Array will be divided in 40:60 hence we get T(2n/5) for 40 division : i.e 40*n/100 and T(3n/5) for 60 division : i.e 60*n/100.The term n comes as addition because at every step we partition the array and Paritioning takes n time. Hence combining both of them we get T(2n/5) + T(3n/5) + n