Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### daihan's blog

By daihan, 7 months ago, ,

In a problem i needed just unique elements , so i used set but got time limit exceeded but Later used vector unique + resize() and got AC . I don't know how is this possible , because both code has time complexity of O(nlog(n));

    set<int> st;

for(int i=0;i<n;i++)
st.insert(i); // log(n)


This code time complexity: O(nlog(n+container size) )

===================================================================================

       vector<int> vct;
for(int i=0;i<n;i++)
vct.push_back(i);

sort(vct.begin(),vct.end());  // nlogn
auto it=unique(vct.begin(),vct.end()) ;  // n
vct.resize(it - vct.begin() ); // n


This code time complexity: O(nlog(n) + n + n) which is approximately equals to O(nlog(n) + n) . Am i wrong in calculating Time Complexity? nlogn for sorting and one n for unique function call , another n for resize() method call

So , O(nlog(n+container size) ) is almost equals to O(nlog(n) + n) but why they depicts different scinario ?

• -7

 » 7 months ago, # |   0 Constant factor.
•  » » 7 months ago, # ^ |   0 Constant factor with which ? Vector or Set ?
•  » » » 7 months ago, # ^ |   0 Each structure has a different constant factor. O-notation just discards them.
 » 7 months ago, # | ← Rev. 3 →   0 set has C1 * n * log Nvector has C2 * n * log NС1 is much bigger than С2
•  » » 7 months ago, # ^ |   0 Where these C1 , C2 comes from ?
•  » » » 7 months ago, # ^ |   0 From their implementation.
 » 7 months ago, # |   +3 O(n * log n) is asymptotic time complexity notation not the exact time complexity for both operations as you told. In asymptotic TC notation we just compute the proportional term of input size and ignore the constant factors which does not change with input size. See This link for details.