We considered a proof that the expected worst case running time of the randomize

Question

We considered a proof that the expected worst case running time of the randomized quicksort algorithm is Theta(n log n). The analysis used an integral approximation for a summation that we have not studied in this class. There is a proof of this result that does not rely on this method. The proof is based on the following observation. With probability 1/2 the pivot selected will be between n/4 and 3/4 (i.e. a good pivot). Also with probability 1/2 the pivot selected will be between 1 and n/4 or between 3n/4 and n (i.e. a bad pivot). State a recurrence that expresses the worst case for bad pivots. State a recurrence that expresses the worst case for good pivots. State a recurrence that expresses the expected worst case by combining the first two recurrences. Prove by induction that your recurrence is in O(n log n).

Explanation / Answer

(1,2).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.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.

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

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.