What is the time complexity of building a binary heap from n unordered elements using the bottom-up heapify method?
Correct answer C. O(n)
Explanation
Most nodes are near the bottom of the heap, where sift-down has very little distance to travel; only a few nodes near the root may move O(log n) levels. Summing these costs gives a total that is linear in n. Inserting the elements one by one with sift-up can cost O(n log n), which is why the bottom-up method is preferred.
Answer checked How we write and check questions
Discussion