# Recurrence relation of quicksort depending on its pivot

I understand how the recurrence relation of quicksort is

$$T(n) = 2T(n/2)+\mathcal{O}(n)$$,

but if we are guaranteed a certain pivot, for example $$n/4$$th smallest element to be the pivot every time, how would it affect the recurrence relation? I would love some insight on how to approach analyzing such performance.

• Your recurrence relation only holds if the split is always even. Feb 5 '19 at 2:34

When the 4th smallest element is always chosen as a pivot then the recurrence relation is $$T(n) = T(n/4)+T(3n/4) + \mathcal{O}(n).$$

If we look at the recursion tree we will see that the left branch has $$\log_4 n$$ depth and the right has $$\log_{4/3} n$$ depth. At each step, until the leftmost branch terminates, the sum of levels is equal to $$cn \in \mathcal{O}(n)$$, for the remaining the levels the sum $$\leq cn$$. Therefore in the worst case calculation, if we assume all have depth $$\log_{4/3} n$$ and have $$cn$$ cost then the cost is;

$$c n \log_{4/3} \in \mathcal{O}(n\log n)$$

• Note: A would like to draw the recursion tree, but it is hard. See 1/10:9/10 image from Cormen et.al's book. You may replace 9 with 3 and 4 with 10. Feb 5 '19 at 15:33

In quicksort the recurrence relation solely depends on the pivot element. The reason we have it's time complexity as O(n^2) rather than O(nlogn) is the possibility of chosing the worst possible element in every iteration (arises in scenarios when a sorted array is given). In case the pivot element is decided in a way that it divides the array in any way (even in 9/10 and 1/10 or any such unequal partition) then too the complexity of the quicksort would decrease to O(nlogn).

• This doesn’t quite answer the question: what happens to the recurrence relation, and how to analyze it? Feb 5 '19 at 7:01