# 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. – Yuval Filmus Feb 5 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)$$