how does building a heap take O(n) time ?
we need to process n elements and for each element , we first insert it into the vector and then compare it with parent and swap if required and this goes on , so the complexity should be O(n * log (n)) ?
Heap complexity
hi shubham
by direct analysis it suggests that time complexity is O(n*log(n))
but there is a mathematical proof which proves that time complexity is O(n).
if you want i can share that proof.
Yes , please share the proof.
Hey Shubham
You can look at this…
As the height increases as we move upwards along the tree, so, for finding the complexity of building a heap, we have to find the number of nodes having height h. The Heapify function we use inside buildheap takes different time for each node.
1 Like
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.