complexity about going from beginning to end and back through a vector

Question

Hi All

I am trying to be familiar with the complexity evaluation of algorithms. In general I think that is a good/elegant practice, but in the specific I need it to express time complexity of my C++ code.

I have a small doubt. Suppose I have an algorithm that just reads data from the beginning of a std::vector until the end; then it does the same starting from the end to beginning (so are 2 cycles for indexes "From 0 To N" followed by "From N To 0" ).

• I said to myself that the complexity for this stuff is O( 2N ): is this correct?
• Once I reached the beginning, suppose that I want to start reading again all data from beginning to the end ( passing in total 3 times the vector ): is the complexity O(3N) ?

It is maybe a stupid doubt, but I would like to have someone opinion anyway about my thinking process.

Kind Regards Afg

Answer 1

Big-O notation simply means:

f(n) = O( g(n) ) if and only if f(n) / g(n) does not grow to infinity as n increases

What you have to do is count the number of operations you're performing, which is f(n), and then find a function g(n) that increases at least as fast as f.

In your example of going one way and then back, the number of operations is f(n) = 2n because each element is read twice, so, you can choose g(n) = n. Since f(n) / g(n) = 2n / n = 2 obviously does not grow to infinity (it's a constant), you have an O(n) algorithm.

It's also an O(2n) algorithm, of course : since the "grow to infinity" property does not change when you multiply g(n) by a constant, any O( g(n) ) is also by definition an O( C g(n) ) algorithm for any constant C.

And it's also an O(n²) algorithm, because 2n / n² = 2 / n decreases towards zero. Big-O notation only provides an upper bound on the complexity.

Answer 2

It's important to get a working feel for Big-O notation. I'll try to convey that...

As you say, your algorithm intuitively is "O(2N)", but imagine someone else writes an algorithm that iterates only once (therefore clearly O(N)) but spends twice as long processing each node, or a hundred times as long. You can see that O(2N) is only very weakly suggestive of something slower than an O(N) algorithm: not knowing what the operations are, O(N) might only be faster say 50.1% of the time.

Big-O becomes meaningful only as N gets huge: if your operations vary in length by say 1000:1, then the difference between an O(N) and O(NlogN) algorithm only becomes dominant as N exceeds 1000 squared (i.e. 1000000). So, Big-O notation is for reasoning about the cost of operations on large sets, in which linear factors like 2x or 10x just aren't considered relevant, and they're ignored.