🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← Quiz: Heaps and Heap Sort Internals: all 15 questions

Quiz: Heaps and Heap Sort Internals · Question 6 of 15

Why does heapify (sifting down from the last parent to the root) take O(n) and not O(n log n)?

Why does heapify (sifting down from the last parent to the root) take O(n) and not O(n log n)?

  1. A.Because it skips half of the comparisons by luck
  2. B.Most nodes are near the bottom and can sink only a few levels; the total work sums to less than n
  3. C.Because sift down is O(1)
  4. D.It actually takes O(n log n)
Answer & explanation

Correct answer: Most nodes are near the bottom and can sink only a few levels; the total work sums to less than n

Half the nodes are leaves (0 work), a quarter sink at most 1 level, and so on; the series is bounded by n.

Can you get the rest right without peeking?

Take the timed Quiz: Heaps and Heap Sort Internals quiz free. Pass it to earn XP and count towards your certificate.

Start the quiz →