3. Let A be an array of n distinct numbers. In the lecture, we have learnt that

Question

3. Let A be an array of n distinct numbers. In the lecture, we have learnt that finding the kth smallest number of A, for any k, can be done in O(n) time. Suppose that we now want to know more about the array. In particular, we want to finod out the 23th smallest numbers of A, for all j 0,1,.., |logn]. (That is, we simultaneously want know which numbers are respectively the 1st, the 2nd, the 4th, the 8th, .. smallest numbers of A.) Design an O(n)-time algorithm to accomplish the above task. 4. Similar to Question 3, but this time we want to get the first vn smallest numbers of A in sorted order Show that the above can also be done in O(n) time.

Explanation / Answer

We can use 'median of the median' algorithm to do the task.

We first prepare an array of all 2^j th elements and then traverse through it to find out that smallest element by following these steps:

Let 2^j be k,

Dividing the array by 5 assures a worst-case split of 70-30 and at-least half of the medians are greater than the median-of-medians, hence at-least half of the n/5 blocks have at-least 3 elements and this gives a 3n/10 split, which
means the other partition is 7n/10 in worst case.That gives time complexity is
T(n)=T(n/5)+T(7n/10)+O(n).T(n)=T(n/5)+T(7n/10)+O(n).

So Max complexity is O(n)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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