2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Your recurrence relation only holds if the split is always even. $\endgroup$ – Yuval Filmus Feb 5 at 2:34
2
$\begingroup$

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)$$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – kelalaka Feb 5 at 15:33
0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ This doesn’t quite answer the question: what happens to the recurrence relation, and how to analyze it? $\endgroup$ – Yuval Filmus Feb 5 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.