Q51: Best case of Quick Sort

This is in continuation of Question #50

Question #51: What is the best case complexity of the quick sort?

1. O(n)
2. O(n³)
3. O(n²)
4. O(n log(n))

Solution: In the best case, we will always have the pivot element as the median, and it will divide the two sub-arrays into two equal parts. Hence, the recursive equation will be:

• T(n) = T(n/2) + T(n/2) + n
• T(n) = 2T(n/2) + n
• T(n) = 2( 2*T(n/4) + n/2) + n
• T(n) = 4T(n/4) + 2n
• T(n) = 8T(n/8) + 3n
• …
• T(n) = n*T(n/n) + log(n) * n
• T(n) = O(nlog(n))

Hence, the correct answer is D