# How to state a recurrence that expresses the worst case for good pivots?

The Problem Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and $\frac{3n}{4}$(a good pivot). Also with probability $\frac12$ the pivot selected will be between 1 and $\frac{n}{4}$ or between $\frac{3n}{4}$ and $n$(i.e. a bad pivot)

1.State a recurrence that expresses the worst case for bad pivots.
2.State a recurrence that expresses the worst case for good pivots.

My Work: I understand the overall idea of quicksort - pivot all the elements around the pivot(less-> to the left, right -> to the right) and repeat the process for the elements to left of the pivot and for the elements to the right of the pivot
Here is the recurrence I came up with for 1 -$T(n) = \begin{cases} c & \text{if$n$is 1} \\ T(n-1) + n, & \text{if$n$is > 1} \end{cases}$
I was able to work out this recurrence by reasoning that if I just chose the worst possible pivot(either greatest or least), I would have to traverse through all the elements(the $n$) and then repeat this process for the rest of the elements(n-1)

I am having trouble with coming up with a recurrence that expresses the worst case for good pivots. The two I came up with is if you choose a pivot of $\frac{n}{2}$ and if you choose a pivot of $\frac{n}{4}$

The recurrence for a pivot of $\frac{n}{2}$ would be $T(n) = \begin{cases} c & \text{if$n$is 1} \\ 2T(\lfloor(n/2)\rfloor) + n, & \text{if$n$is > 1} \end{cases}$
I wasable to reason this out because if you had a pivot of $\frac{n}{2}$, you have to evaluate all the elements with regards to the pivot(the $n$) and then partition the equal proportions to the left and to the right of the pivot.

The recurrence for a pivot of $\frac{n}{4}$ would be $T(n) = \begin{cases} c & \text{if$n$is 1} \\ T(\lfloor(3n/4)\rfloor) + T(\lfloor(n/4)\rfloor) + n, & \text{if$n$is > 1} \end{cases}$

Which one of these would express the worst case for good pivots?

## 1 Answer

The worst case for the good pivot is one where you split in 3n/4 and n/4. Splitting into two equal parts of size n/2 is the best possible case you can have. On the other hand, for the good pivots, 3n/4 leaves you with the largest subproblem possible.

• Can you explain why the split of 3n/4 and n/4 is better than the split into two n/2? To me it seems the same because you're still going to eventually have to sort everything – committedandroider Apr 26 '15 at 21:18
• The 3n/4 split is not better. It's worse because both the depth of the recursion tree and the number of elements will be larger than with a perfect n/2 split. – Jordi Vermeulen Apr 26 '15 at 21:28
• The next question asks state a recurrence that expresses the expected worst case by combining the first two recurrences. Would that recurrence just be the split into two n/2? – committedandroider Apr 26 '15 at 22:27
• Once again, splitting into parts of size n/2 is not the worst case. It never is. I am unsure how you're supposed to express expected behaviour in a recurrence, but the point is that either case has a probability of 0.5. You could assume that you get alternating good and bad pivots, and substitute the good recurrence into the bad recurrence. – Jordi Vermeulen Apr 27 '15 at 7:53