Erasing an element in a vector is O(n) as we have to remove the element and still need to shift all successive elements to fill the gap created. If a vector has n elements, then in the worst case we will need to shift n-1 elemets, hence the complexity is O(n).
in your example , vec[i] will give 3
4 Likes
“Your code fail for consecutive 5s”
I know. 
. I didnt want to put any of implementation, as i felt some people would get confused with the “i–” thing there. 
(And i was also kinda unsure)
“Time complexity = O(nlog(n)) (Not sure)”
Did it ran for 10^6 ? I feel O(NlogN) would run for 10^6, but O(N^2) would fail. The reason why it passes 10^5 despite being O(N^2) might be as its not strictly O(N^2) and number of instructions might lie “just in” range of getting executed. To confirm this, we can take 10 inputs from 10^5 to 10^6 in pattern of 2x 10^5, 3x10^5 …9 x 10^5 etc.
Also, @olofmeister - Thanks dude. More than the answer to your question, i gained another perspective by your answer. I am grateful to you too for sharing your views and procedure.
if all you want do is to remove item with value = 5, can’t this code suffice?
.
.
#include <algorithm>
std::remove_if ( vec.begin(), vec.end() , [](int i)
{
return ( i == 5 );
});
I do have a doubt though! does this sort of STL’s use impact runtime performance?
Hey, can you look up at this code 55kYc4 - Online C++0x Compiler & Debugging Tool - Ideone.com and tell why it takes 0.44 seconds to complete.
I just implemented what vijju said in second part.
I did i=0 inside the code, as the vector was getting resized and hence there was a runtime error for i==vec.size().
1 Like
1aMESY - Online C++0x Compiler & Debugging Tool - Ideone.com a little bit updated code,just to show you the number of iterations are only 10^5, still time taken is 0.44 seconds.
Its definately not O(n), else it would be done in 0.01 seconds.
1 Like
Check this link runtime error is now fixed. VO0i9N - Online C++0x Compiler & Debugging Tool - Ideone.com
Partially correct.
okay then what is that partially incorrect in it … it’s fully correct .
Np, and i agree with you, for n=10^6, it goes beyond 5 seconds, so it is not O(nlogn).
1 Like
Can we claim it’s complexity to be O(n^2)?
3x10^5 is the upper bound, it takes 4.77 second to run for it.
I guess, in 1 second, we have about 10^7 instructions, so for n=3x10^5, we are executing 4.7x10^7 instructions, maybe u can compare different values and find out the order based on it.
1 Like
Yes, olofmeister is correct. The complexity is O(N^2). The procedure you described hints at it being O(N^2).
Then what’s the complexity?
I feel it passes 10^5 because we are doing just a single operation, under which we must take other factors in consideration. Instructions per second are around 10^8 to 10^9, so constant factors cannot be neglected. We will have to go onto finer details like calculating exact operations using O(n(n-1)/2) etc.
Had it been part of some code, then it would have defintely given a TLE. Remember, its just one of the segment of a program, running for only one of the possibly multiple test cases.
1 Like
The procedure described by sources of shifting elements (n-i) elements forward and etc. dont give me any logarithmic angle. I mean, how can that be logarithmic? It seems more closer to N(N-1)/2
So it’s somewhere in between of nlog(n) and n^2 but closer to n^2
Whatever it may be, the thing is that it was the reason i got TLE and was cluelessly frustrated for an hour. I though the entire code is O(N) with deletion being only O(1) complexity…
That logic was to be used to solve a practice problem on hackerearth. I went on using vectors but got lots of TLE and hence got confused.