I am not able to understand the rigorous proof of why build heap takes O(n). Can someone please explain it to me?

See this link.

I am not able to understand the rigorous proof of why build heap takes O(n). Can someone please explain it to me?

Hi,

What have been your attempts to work out the proof? There’s a lot to be gained from this so there’s no point in spoiling it. You might also be very close but just missing one small idea so someone can nudge it in the correct direction.

It’s useful to also isolate which bit causes the most friction in understanding. Is it the convergence? The manipulation of the summation boundaries? Or the general motivation? It’s easier to give more focused feedback with this information as well.

1 Like

I am not sure how to find the cost of sifting down while constructing the heap.