I want you to now remember the following partitioning problem we considered a wh

Question

I want you to now remember the following partitioning problem we considered a while ago. You are given a list L of length n and asked to partition the elements of L into two sublists L_1 and L_2 such that n/3 |L_1|, |L_2| 2n/3 and all elements in L_1 are less than or equal to all elements in L_2. We designed a simple, randomized (Las Vegas) algorithm for this problem that ran in O(n) expected time. Let us replace the call to partition in the code for quickSort given above by a call this Las Vegas algorithm. After we obtain a partition (L_1, L_2) by calling this Las Vegas algorithm, we can simply call quickSort on L_1 and then on L_2. Now we have a randomized (Las Vegas) version of quickSort. I would like to analyze the expected running time of this algorithm. Write down a recurrence relation for the expected running time of this randomized version of quickSort. Solve this recurrence to obtain an upper bound on the expected running time of this randomized version of quickSort.

Explanation / Answer

I want you to now remember the following partitioning problem we considered a wh

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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