[Solved]: How to state a recurrence that expresses the worst case for good pivots?

Problem Detail: 

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?

Asked By : committedandroider

Answered By : Jordi Vermeulen

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41867

3.2K people like this

 Download Related Notes/Documents