educative.io

Educative

Question about the time complexity

I don’t understand that when we inserted at most ‘K’ or one element from each of the ‘N’ rows to the heap, the time complexity is O(min(K,N))

Shouldn’t it be like log1 + log2 + ... + log(min(K, N)) = log(min(K, N)!)

Can someone explain this?

1 Like

Hi @Haomin,

O(min(K, N) ) is the time complexity of the for loop to store values in the minHeap. The size of the min-heap will be a minimum of K and N because, when the K is less than the number of columns (N), we need only the K number of nodes to find the k’th smallest element in a sorted matrix, but if the K is greater then N we’ll need only N number of nodes because after every iteration in while loop, one of the nodes will be replaced by a new number.

1 Like

So the time complexity should be min(K, N) x inserting time in minHeap, how to simplify it with O(min(K, N) ) ?

2 Likes

I agree with Nicole. it should be: O (min(K, N) x lg(min(K,N))


Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Kth Smallest Number in a Sorted Matrix (Hard) - Grokking the Coding Interview: Patterns for Coding Questions