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?
