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 -
- Building a heap is
O(n)
, but this function is called k times via theremoveMin()
function, so complexity of this should beO(k*n)
-
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 itO(k*logn)
?
Based on the above steps, total time complexity should be O(k*n)
, so how is O(n+klogn)
?