daihan's blog

Set Vs Vector unique+resize()
By daihan, 5 years 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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Constant factor.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Constant factor with which ? Vector or Set ?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
5 years 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

→ Reply
»
5 years 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.

→ Reply