Is this code O(N) or O(1)

Question

vector<int>::iterator it;
vector<int> p;
p.push_back(4);
p.push_back(5);
p.push_back(6);
p.push_back(7);
it = p.begin() + 2;
cout << it << endl;

Is this O(N) or O(1)? And why?

Answer 1

It is O(1) because it has constant number of operations.

Answer 2

Depends on the operations you're looking at, but it should be O(1).

Creating the vector and iterator are constant time, as it's memory allocation. Pushing onto the vector is constant time depending on implementation, but I believe the STL impl is constant time. Four operations of constant time pushing are constant. Setting the iterator is constant time, because getting the begin of the vector is constant and addition is constant.

Finally, printing is constant time, so the whole process is O(1).

Answer 3

It is O(1). In order for O(n) or O(not 1) to even be relevant you need to have at least one variable that (when changed) will impact the performance of your algorithm by changing the total amount of iterations or work that needs to be done.

Answer 4

Each operation is (amortized) constant time, so the entire thing is constant time.

Answer 5

It is O(1) since its number of operations are fixed. For something to be O(N) there has to be linear variability in how many operations are performed.

Answer 6

It is O(c) where c is a constant because nowhere is a non constant-time operation, but is it O(1)? I guess it is assumed the cost of all these operations is 1.

Answer 7

Really it depends on what push_back and begin do internally. If either (or both) is O(n) then the whole thing is O(n), because O(N) dominates O(1) and there is a constant number of them. Same goes for anything greater than O(1), such as O(nlogn). If both are O(1) then the whole thing is O(1) due to there being a constant number of them. Most likely it is O(1) since push_back and begin are usually very simple and written to be O(1).

Answer 8

Pushing onto a vector does not happen in constant time in the worst case. If your vector is full, it will have the copy the contents into a larger vector before continuing. This is an O(n) operation.

Answer 9

My guess is you're asking about p.begin() + 2; (most people care about searches more than, say, insertion).

It's simple pointer arithmetic so yes, it's constant-time O(1). If this was a linked-list traversal, then it would be O(n). Of course, this assumes that the implementation of the integer vector list is akin to an array -- namely they're all in contiguous blocks of memory.

See: http://www.cprogramming.com/tutorial/stl/iterators.html

Iterators are often handy for specifying a particular range of things to operate on. For instance, the range item.begin(), item.end() is the entire container, but smaller slices can be used. This is particularly easy with one other, extremely general class of iterator, the random access iterator, which is functionally equivalent to a pointer in C or C++ in the sense that you can not only increment or decrement but also move an arbitrary distance in constant time (for instance, jump multiple elements down a vector).

Answer 10

As everybody else said, it is O(1). However, if you meant to write something like this:

vector<int>::iterator it;
vector<int> p;
p.push_back(4);
p.push_back(5);
p.push_back(6);
p.push_back(7);
...
p.push_back(n);
it = p.begin() + 2;
cout << *it << endl;

i.e.:

for (int i=4;i<=n;i++)
  p.push_back(i);

then it would be O(n), since vector::push_back() and vector::begin() are O(1) and vector::push_back() is executed n-3 times.

Answer 11

I think the answer depends on how the '+' operator works. If it is simple pointer arithmetic then it is O(1).

Answer 12

It can be anything from O(1) to exponential and really depends on implementation of push_back.

Answer 13

As long as vector's functions are implemented in a deterministic fashion (which they should be or something is seriously wrong), it's O(1). Period.

The entire discussion about the implementation of vector's functions is moot because the value of n is known. This snippet will always run the exact same code and take the exact same number of clock cycles on a given machine with a given vector implementation. Swap out the machine or the implementation and it will still be O(1); it will just take a different amount of constant time.

Remember, folks, O(1) doesn't necessarily mean "fast." It means "very scalable."

Answer 14

Are you asking about it = p.begin() + 2;?

Accessing elements of a vector in this way is amortized constant time (from a guarantee on Random Access Iterator), just like writing p[2]. So, statements like it = p.begin() + n; are O(1).

It's not correct to talk about O(N) without telling us what N is, but I'm assuming you're talking about the array lookup with N being the number of elements. Also you probably mean cout << *it << endl; in the last line.