Hey guys! I was trying out a question on vector, and am stuck on this concept.
Suppose i write this code-
for(i=0;i< vec.size();i++)
{
if(vec[i]==5)
{
vec.erase (vec.begin()+i);//Statement 1. Erasing element at index i.
}
}
Suppose that number of elements, N, is ~10^6, and it is the worst case (i.e. every element is 5 and has to be deleted). With reference to above (and any other necessary assumption needed), please tell-
The element i will get if a use “cout<< vec[i]” after statement 1. Meaning, if the vector is [1,2,5,3,4], and now 5 is deleted. So printing “vec[i]” would give me 2 or 3? (i feel it would be 3 but not sure)
Time complexity of above. I searched and found that vec.erase(vec.begin() , vec.end() ) has a linear time complexity, but is it true even for cases when only 1 element is to be deleted? Or is it O(1) for such a case? In other words, i want to ask if the overall time complexity of the code segment in question (in worst case) is O(N) or O(N^2)?
@vijju123 Your code fail for consecutive 5s, corrected code:
for(i=0;i< vec.size();i++)
{
if(vec[i]==5)
{
vec.erase (vec.begin()+i); // Statement 1. Erasing element at index i.
i--;
if(i == vec.size()-1) // escape from the runtime error :p
break;
}
}
erase operation in vector does two tasks:
Destruct ith element
Move all elements after ith element
>> Yes, you are right “cout<< vec[i]” should print 3.
>> The time complexity is linear for one operation. Not same if all elements are 5.
“Linear on the number of elements erased (destructions) plus the number of elements after the last
element deleted (moving).”- cplusplus refrence
If you have n elements and all are 5 then the time complexity will be around O(nlog(n))
delete n elements
you’ll move n-i elements
You need to backtrack using “i–” to check if the current indexed element is 5.
Time complexity > O(nlog(n))
For different values of n runtime is listed below
n time(*10^(-6) sec)
10 1
100 4
1000 30
10000 3645
100000 451476
10^6 TLE
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
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.
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.
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.
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
. 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)