2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – committedandroider Apr 26 '15 at 21:18
  • $\begingroup$ 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. $\endgroup$ – Jordi Vermeulen Apr 26 '15 at 21:28
  • $\begingroup$ 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? $\endgroup$ – committedandroider Apr 26 '15 at 22:27
  • $\begingroup$ 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. $\endgroup$ – Jordi Vermeulen Apr 27 '15 at 7:53

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.