educative.io

Educative

Initializing the min-heap with all numbers will take O(N)

Hey guys,

I am wondering why the time complexity of initializing heap with all numbers is O(N), thanks for your help !!!

H

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5696381570252800

Hello! you can find here the answer you are looking for Time Complexity of building a heap - GeeksforGeeks

1 Like

Hi @Nicole,

Firstly we use a max heap and not a min heap.

The reason the time complexity is O(N) is because we put in the max heap k elements in order to find the K smallest number so in the case where K == N we would put all N number is the max heap thus having a time complexity of O(N).

Hope this helps.