Question

4. [30 pts:10+9+11] a) You are given traffic data (number of page hits) for n websites for some time period. (n is a large number, in the order of hundreds of thousands.) You are asked to print the top k websites with greatest amount of traffic (k is much smaller than n). Which of insertion sort, mergesort quicksort, or heapsort may be used to devise the fastest (in worst case) algorithm for this task? What would be its worst case big O running time, in terms of n and k? (Note: You cannot modify the steps in any of these known sorting algorithms, but you can stop it as soon as you get the top k. And you can use the running times of all involved known entities without derivation.)

Answer 1

elements m e nts wi th index ele than k Yoot ay in dex utn unhi

Sige bui ld nein heap tox (fntin de x--K· index <c.ze , r, dex ++) del) t- K)

ahais k- element On