daihan's blog

By daihan, 3 months ago, In English,

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 ?

 
 
 
 
  • Vote: I like it
  • -7
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Constant factor.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Constant factor with which ? Vector or Set ?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Each structure has a different constant factor. O-notation just discards them.

»
3 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

set has C1 * n * log N

vector has C2 * n * log N

С1 is much bigger than С2

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.