0

You intend to run heapify on an array of n integers, in order to turn it into a heap in-place. How long will this operation take, in the worst case? (choose the tightest possible bound)

Options are:
a) O(n)
b) O(nlogn)
c) O(nlog^2n)
d) O(n^2)

I tried this out and got the following: Since we have at most n nodes we have O(n) and since we need to move up and compare only the height of the tree times we get O(logn) thereby giving us O(nlogn). But this solution is wrong.

Then I thought maybe we don't compare the only the height of the tree times because a smaller node can be placed on the right side of the tree forcing us to go all the way to the right side and I marked O(n^2). And that was wrong too. Any suggestions?

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
CODER1030
  • 39
  • 4
  • Reasoning about complexity requires reasoning about a specific algorithm (different algorithms to compute the same function might have different complexities). You have not stated the algorithm for which you're trying to answer this question. – user2407038 Jul 11 '21 at 02:53
  • Yeah. Thats why Im confused. They havent specified anything in the question. Im pretty sure its not O(n) because there have to be 2 components 1) the comparision and 2) the number of heap elements you do it for. – CODER1030 Jul 11 '21 at 02:55
  • 1
    [Heapification](https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap) can be done in O(n). – John Kugelman Jul 11 '21 at 03:08
  • Of course, I am being overly pedantic. There are many well known heapify algorithms, all O(n). But it seems the goal here is not just to find the answer, but to learn how to derive it yourself. My point is just that your reasoning should apply to the specific properties of the algorithm - you should first write out the algorithm and go from there. – user2407038 Jul 11 '21 at 03:15
  • 3
    Does this answer your question? [How can building a heap be O(n) time complexity?](https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity) – trincot Jul 11 '21 at 07:06

0 Answers0