Suppose that, in thealgorithm for selecting the kth smallest element in a set of

Question

Suppose that, in thealgorithm for selecting the kth smallest element in a set of sizen,
we had partitioned the set S into n/3 chunks of size 3 each(instead of n/5 chunks of size 5 each).
Analyze the modified algorithm, and give the recurrence relationgoverning its running time.
What is the order of complexity of the solution to the recurrence ?Briefly justify your answer. Suppose that, in thealgorithm for selecting the kth smallest element in a set of sizen,
we had partitioned the set S into n/3 chunks of size 3 each(instead of n/5 chunks of size 5 each).
Analyze the modified algorithm, and give the recurrence relationgoverning its running time.
What is the order of complexity of the solution to the recurrence ?Briefly justify your answer.

Explanation / Answer

The recursive call would be on a problem of size n/3, and wouldtherefore take time T(n/3). Suppose that this first recursive callreturns as answer x1, i.e., x1 is the medianof the set S1 (where | S1| = n/3). LetS<= (respectively, S>) denote the setof elements that are <= x1 (respectively,>x1). The key observation is that neitherS<= nor S> can have size smaller than(| S1|/2) + (|S1|/2) = n/3. This, togetherwith the fact that |S<=| + |S>| = n,implies that neither S<= nor S> canhave size greater than n n/3 = 2n/3, but the size of eithercould be as large as 2n/3. This means that in the worst case thesecond recursive call costs T(2n/3). But then the overallrecurrence would be of the form T(n) = T(n/3) + T(2n/3) +cn, the solution is T(n) = O(n log n).

I hope this will helpfull toyou

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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