(10 points) You run heapsort on n 2A numbers, timing its performance for each ph
ID: 3725156 • Letter: #
Question
(10 points) You run heapsort on n 2A numbers, timing its performance for each phase. You may assume (even if it isn't true) that for this size input, the runtime is completely stable, that is, don't need to worry about some of the "real world" issues we saw in our lab. The build-heap part takes B seconds, and the rest of the sort takes S seconds. Next, you run the same program, but on a different set (and different size set) of numbers, on a machine which is three times as fast. It takes B/6 seconds to build the heap. What is the best guess for how long the rest of the sort will take on that faster machine? you
Explanation / Answer
Building a heap takes O(n) time. So 3 times faster machine will take B/3 time on same data set. But here it is taking B/6 time it means dataset is half the size of dataset taken initially which is n = 223.
Now , S for the first machine = n log2 (n) = 224 log2 (224 ) = 24*2* 223 log2 2 = 24 * 2 * 223 = 48 * 223
So best guess of S for this 3 times fatser machine =n log2 (n) = 223 * log2 (223 ) = 23 * 223 (here n = 223 )
= (23 * S)/48
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.