Can someone explain the complexity of this code?

1

we need to find the k smallest pairs

int kpairs(vector<int>&A,vector<int>&B,int k){
    int n=A.size(),m=B.size();
    priority_queue<int> pq;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int sum = A[i]+B[j];
            if(pq.size()<k){
                pq.push(sum);
            }
            else{
                if(pq.size()==k){
                    if(sum<pq.top()){
                        pq.pop();
                        pq.push(sum);
                    }
                }
            }
        }
    }
}
2

O(nm\log{k}). The priority queue will contain k elements, and the for loops iterate nm times.

3 Likes
3

I think for priority queue it will be klogk because for inserting k elements will take O(k) and for heapify process take O(logk) so I think the overall complexity is O(klogk) and for this quest is O(nmklogk).
can you correct me where i am going wrong?

4

The k elements aren’t inserted at every single iteration. At each iteration, you push and pop only once, so for each iteration it takes O(\log{k}) time.

2 Likes
5

but at first we insert k elements in priority queue so that time it will take klogk after that we only take care about single element then i think it will be logk.

so suppose if I insert N elemnts in priority queue then I will take NlogN so I think the for klogk case is correct.