Given a set of n numbers, we wish to find the k largest in sortedorder. State, i

Question

Given a set of n numbers, we wish to find the k largest in sortedorder.
State, in terms of n and k, the time complexity of the bestalgorithm that implements each of
the following methods (you do not need to prove or justify youranswer).

1) Sort the numbers, and listthe k largest. 2) Build aMax-Heap data structure from the numbers,
and call Extract Max k times. 3) Use the selection algorithm to find the kth largest number,
partition the input around that number, and sort the k largestnumbers.
Given a set of n numbers, we wish to find the k largest in sortedorder.
State, in terms of n and k, the time complexity of the bestalgorithm that implements each of
the following methods (you do not need to prove or justify youranswer).

1) Sort the numbers, and listthe k largest. 2) Build aMax-Heap data structure from the numbers,
and call Extract Max k times. 3) Use the selection algorithm to find the kth largest number,
partition the input around that number, and sort the k largestnumbers.

Explanation / Answer

   Sort using Merge-Sort in O(n log n) time and printthe last k elements of   the sorted list in O(k)time. The worst-case running time is O(n log n) +O(k) =O(n logn).

2)

Building a max-priority queue takes O(n) time andExtract-Max takes O(log n) time. The worst-case running timeis O(n) + k.O(log n) = O(n+k log n).

3)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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