educative.io

Educative

Explanation of Time Complexity for "Find the k Smallest Elements in an Array"

I don’t understand the explanation provided for finding the time complexity of the “Find the k Smallest Elements in an Array” challenge -

The time complexity of building a heap is O(n), as discussed in the implementations.
Furthermore, removing the k smallest elements takes a time complexity of O(klogn)

Therefore, we can say that the total time complexity is O(n+klogn)

From what I understand -

  1. Building a heap is O(n), but this function is called k times via the removeMin() function, so complexity of this should be O(k*n)
  2. Removing the smallest element in the heap is a constant time operation because you just replace the root node with the last leaf node, and since this is done k number of times, this becomes O(k). So how is it O(k*logn)?

Based on the above steps, total time complexity should be O(k*n), so how is O(n+klogn)?

Hello everyone, came here for the same doubt as @Manish_Giri.

Also it wouldn’t be most time efficient to iterate(minHeapefy) over the parents nodes just once to order the heap and then pop the min nodes ?

Something like this:

image