educative.io

Educative

Need some help on Time Complexity of Building Heap

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

@Jason1, that is correct.

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