You need to select k = 15 most successful lottery winners from an unordered arra

Question

You need to select k = 15 most successful lottery winners from an unordered array of winning records for n = 100, 000, 000 web lottery participants all over the world. Each record contains the winner’s name and the winnings specifying how successful this winner is. You know two options for selecting the k higher-rank individuals:

(a) to run k times quickselect with linear processing time, Tqselect(n) = cn, in order to sequentially fetch the participants having the desired ranks n, n ? 1, . . . , n ? k + 1), or

(b) to run once quicksort with n log n processing time, Tqsort = cn log2 (n), to sort the array in ascending order of winnings and fetch the k higher-rank participants.

Providing the factors c are the same for both the algorithms and the fetching time is negligibly small comparing to the sorting time, which option does result in the fastest selection?

Explanation / Answer

Solution:

Option b is better here.

Explanation:

a)

The quick select algorithm is running k number of times first in which it is fetching the participants with the desired tank which will take O(n) amount of time. which means that the k runs of quick select may take O(n) time.

b)

Quicksort algorithm takes O(n log n) time which will sort the given array in the ascending order and it will fetch the higher participants may take O(1) time.

This proves that option b is faster than the option a since it is taking O(n log n) time.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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