# Can someone explain the complexity of this code?

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);
}
}
}
}
}
}
``````

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

3 Likes

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?

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

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.