In this problem, it says “Given ‘N’ ropes, we need O(N*logN) to insert all the ropes in the heap”, however, in previous problems, it says, to build a heap, it just uses O(N) time. Which one we should mention if we are asked in the interview and how we gonna explain. Thank you all.
3 Likes
Hi @Jason1,
Sorry for the confusion. Building (or initializing) a heap with ‘N’ elements will take O(N) whereas if we insert elements one by one in the heap it will take O(N*logN).
To understand why build a heap will take O(N), please see: https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity
Hope this clarifies your question.
3 Likes
Hi, thank you for your reply. Can I understand that if we use heapq.heapify(array) to heapify an existing array with N elements, the time complexity is asymptotically equal to O(N) based on some complicated math. And if we use
heap = []
for num in array:
heapq.heappush(heap, num)
to build the heap one element by one, which is using O(N*logN) time complexity.
2 Likes
Sorry, I think the time complexity is O(n+nlog(n)), because initialing with array takes O(n), inserting node during while takes o( nlog(n)), is that right? @Design_Gurus
Initializing the heap by adding elements one by one takes O(NlogN). Then the ‘while’ loop takes O(NlogN); hence total complexity will be:
O(NlogN + NlogN) => O(2NlogN) => O(N*logN)
On a side note, O(N + NlogN) is asymptotically equivalent to O(NlogN) as “N < N*logN”.
1 Like