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 ?
Constant factor.
Constant factor with which ? Vector or Set ?
Each structure has a different constant factor. O-notation just discards them.
set has C1 * n * log N
vector has C2 * n * log N
С1 is much bigger than С2
Where these C1 , C2 comes from ?
From their implementation.
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.