1

What is the running time in big-O notation of:

vector.push_back(item)

and

vec.erase(itr)  // itr points in the middle of a vector
user229044
  • 232,980
  • 40
  • 330
  • 338
Jon Smith
  • 11
  • 3
  • 4
    What ideas do you have about this? This site doesn't exist to do your homework for you. – Zeke Dec 08 '10 at 04:43
  • See: http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it – fncomp Dec 08 '10 at 04:44
  • well i want to know what is more efficient and why, and if it when the vector gets bigger and smaller if that effects it at all – Jon Smith Dec 08 '10 at 04:47

3 Answers3

1

O(1) (amortized time, reallocation may happen) in case of push_back()

O(n) in case of erase() i.e Linear on the number of elements erased (destructors) plus the number of elements after the last element deleted (moving).

Prasoon Saurav
  • 91,295
  • 49
  • 239
  • 345
  • so ammortized means that reallocation may happen? – Jon Smith Dec 08 '10 at 04:48
  • "ammortized" is a kind of averaged cost, factoring in the nasty situations... if you add some huge number of elements to the vector, then the number of resizes are typically (but not necessarily) about log_base2(N) - with the copying involved it roughly doubles the work / halves the speed, but O() notation ignores such linear time differences and still considers it O(N). – Tony Delroy Dec 08 '10 at 04:54
  • what if we are talking about the erase of a linked list? is it the same? or is it O(1) because you dont have to relocate? – Jon Smith Dec 08 '10 at 05:02
  • erase from a linked list is O(1), yes. That is, assuming you already know which element should be removed. :) – Karl Knechtel Dec 08 '10 at 05:11
  • @Jon : Its constant time(amortized) at the beginning or the end, or in the middle. – Prasoon Saurav Dec 08 '10 at 05:11
  • @Prasoon: for linked list node removal, it's constant time, not only constant time (amortized) - still a very significant difference if considering worst-case for a single operation. – Tony Delroy Dec 08 '10 at 05:19
  • does having a double or single linked list make a difference in this case? thanks everyone! – Jon Smith Dec 08 '10 at 05:35
  • @Jon: to erase an element from a singly-linked list you have to change the "next" pointer in the previous element, but in general have no way to get there other than iterating there from the head of the list. Consequently, it's an O(N) operation. – Tony Delroy Dec 09 '10 at 03:22
0

For "vector.push_back(item)" its only O(1). And "vec.erase(itr)" O(n) because later elements are shifted down.

Edit: If it points on the middle in the vector, its like O(n/2).

Constantin
  • 8,721
  • 13
  • 75
  • 126
0

From http://www.sgi.com/tech/stl/Vector.html:

A vector is a Sequence that supports random access to elements, constant time insertion and removal of elements at the end, and linear time insertion and removal of elements at the beginning or in the middle.

Tony Delroy
  • 102,968
  • 15
  • 177
  • 252