Time complexity of vector's element deletion.

general
, ,
1

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-

  1. 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)
  2. 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)?
2 Likes
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:

  1. Destruct ith element
  2. 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))

  1. delete n elements
  2. 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

EDIT: For the best case (only one 5 in vector of size 10^6) runtime is 0.00085 sec http://ideone.com/yURIGe

For worst case (all 5s in vector of size 10^6) we get TLE(Runtime > 5 sec)

It seems the Complexity varies from O(nlog(n)) to O(n^2)

5 Likes
3

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
4

Hey, can you look up at this code http://ideone.com/55kYc4 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
5

http://ideone.com/1aMESY 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
6

Check this link runtime error is now fixed. http://ideone.com/VO0i9N

7

@olofmeister thanks for correction.

8

Partially correct. :slight_smile:

9

@only4

“Your code fail for consecutive 5s”

I know. :stuck_out_tongue: . I didnt want to put any of implementation, as i felt some people would get confused with the “i–” thing there. :slight_smile: (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. :slight_smile:

10

okay then what is that partially incorrect in it … it’s fully correct .

11

Np, and i agree with you, for n=10^6, it goes beyond 5 seconds, so it is not O(nlogn).

1 Like
12

Can we claim it’s complexity to be O(n^2)?

13

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
14

Yes, olofmeister is correct. The complexity is O(N^2). The procedure you described hints at it being O(N^2).

15

@only4 no if it was O(n^2), then for n=10^5 it should have been TLE.

16

Then what’s the complexity?

17

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
18

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

19

So it’s somewhere in between of nlog(n) and n^2 but closer to n^2

20

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…:stuck_out_tongue: