2. Consider the Randomized Select algorithm, to find the kth smallest element of

Question

2. Consider the Randomized Select algorithm, to find the kth smallest element of a set as given below. Algorithm Select(set S, integer k): returns item if Isl = 1, return sole element of S z element of S selected uniformly at random Partition s into L (elements z) return z if k IL return Select(L, k) else return Select (R, k ILI- E) (Note that the partitioning step is the same as that in randomized quicksort, and takes linear time.) Determine the expected running time of this algorithm asymptotically, in the manner of our analysis of randomized quicksort

Explanation / Answer

the worst-case running time is (n2). On the other hand, it turns out (and we will prove) that the average-case running time for Basic- Quicksort(averaging over all different initial orderings of the n elements in the array) is O(nlog n).

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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