# Time limit exceeded

what is the time complexity of this code ? help me.

#include<bits/stdc++.h>
using namespace std;

int32_t  main(){
int n,m;  scanf("%d",&n);
vector<int> vs(n);
for(auto &t : vs)scanf("%d",&t);
scanf("%d",&m);
vector<int> va(m);
for(auto &t : va)scanf("%d",&t);

set<int,greater<int>> st;
for(int i=0;i<n;i++){
>            st.emplace(vs[i]);
}
for(int i=0;i<m;i++){
st.emplace(va[i]);
auto it=st.find(va[i]);
int pos=distance(st.begin(),it)+1;
printf("%d\n",pos);
}
return 0;
}
printf("%ld\n",pos);
}
return 0;
}



It doesn’t actually compile, so technically \mathcal{O}(1)

But seriously, approx :

\mathcal{O}(n + m + n log n + m log (n + m) + m (n + m))

4 Likes

m2 for which term

m(m+n) for which term

Set iterator are not random access iterators. So the distance function is O(\text{distance between the iterators}).

3 Likes
for(int i=0;i<m;i++)
{
// ...
int pos=distance(st.begin(),it)+1; // O(n + m)
// ...
}

2 Likes

O(m2) for the find in the loop. not it is set find it takes log(n)

I think that is for distance. I didn’t knew that there was distance available for set Glad that I today learned new thing

Why it take O(n+m) ?

Max distance can be n+m and it is m times

1 Like

okk, thanks for discussion.

As @aneee004 said, distance takes time proportional to the distance between the iterators, which is proportional to the number of elements in the set, which is \mathcal{O}(n + m).

4 Likes

It manually moves the iterator with it++ until it gets to the second provided iterator. If you haven’t noticed, you cannot write it2 = it + 3 or s.begin() < s.end() with set iterators.

These are possible with vector iterators, because they are random access iterators.

4 Likes

oh !,it’s really helpful .thanks for help.