Calculating average case complexity of Quicksort

Question

I'm trying to calculate the big-O for Worst/Best/Average case of QuickSort using recurrence relations. My understanding is that the efficiency of your implementation is depends on how good the partition function is.

Worst Case: pivot always leaves one side empty

• T(N) = N + T(N-1) + T(1)
• T(N) = N + T(N-1)
• T(N) ~ N²/2 => O(n^2)

Best Case: pivot divides elements equally

• T(N) = N + T(N/2) + T(N/2)
• T(N) = N + 2T(N/2) [Master Theorem]
• T(N) ~ Nlog(N) => O(nlogn)

Average Case: This is where I'm confused how to represent the recurrence relation or how to approach it in general.

I know the average case big-O for Quicksort is O(nlogn) I'm just unsure how to derive it.

Answer 1

When you pick the pivot, the worst you can do is 0 | n and the best you can do is n/2 | n/2. The average case will find you getting a split of something more like n/4 | 3n/4, assuming uniform randomness. Plug that in and you get O(nlogn) once constants are eliminated.