2.4 CHALLENGE In lecture we considered a proof that the expected worst case runn

Question

2.4 CHALLENGE In lecture we considered a proof that the expected worst case running time of the randomized quicksort algorithm, is (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 the pivot selected will be between and (i.e. a good pivot). Also with probability the pivot selected will be between 1 and or between 3n and n (i.e. a bad pivot). (1 points) 1. State a recurrence that expresses the worst case for bad pivots (1 points) 2. State a recurrence that expresses the worst case for good pivots. (2 points) 3. State a recurrence that expresses the expected worst case by combining the first two recurrences. (6 points) 4. Prove by induction that your recurrence is in O(nlogn Grading Correctness and precision are of utmost importance. Use formal proof structure for the big-Theta bounds. You will be docked points for errors in your math, disorganization, unclarity, or incomplete proofs

Explanation / Answer

Solution:

1)

In the worst case of the bad pivot can be either of the endpoints, i.e. 1 or n. In both cases, the structure will not be decomposed into 2 structures, but into 1 structure of length n-1, so we have

T(n) = T(n-1) + c; where c is constant time for finding the pivot

2)

The best of all good cases when n is in the mid. So as we see the algorithm improves as the pivot approaches the mid of the array. So the worst case of the best case would be if the pivot is at n/4 or 3n/4. If the pivot is located at either of these points, the array will be divided into two sub-array of length(n/4) and length(3n/4). So the recurrence relation would be

T(n) = T((n-1) / 4) + T(3*(n-1) / 4) + C

I hope this helps, please let me know in case of any doubt.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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