Learning about Big O notation with C++, confused as to whether this is O(n) or O(n2)

Question

I'm learning programming using YouTube and whatever I can find. I stumbled upon some Big O problems and I'm quite confused on one of them.

for (int i = 0; i < n; i++)
    for (int j = 0; j < 2; j++)
        cout << i << " " << j << endl;

My first thought was that it is O(n²) because there are 2 for loops. Then I took a closer look and noticed that the inner for loop only goes from 0 to 2.

From what I understand, Big O looks at the worst case scenario. My thoughts were that if n = 2 then it would result in O(n²) however all other cases result on O(n) which is what is really confusing me.

Could someone please explain why this is O(n²) or O(n)?

Answer 1

It's O(n). When a function f(n) is O(n), it basically means that there are some constants A and B such for each n (at least for large-enough ns):

f(n) <= A * n + B

In other words, constants (multiplicative and additive) do not affect big-O notation. And since 2 is a constant (it does not depend on n), it is not reflected in the big-O notation.

In your case, the function f is the time complexity - i.e. how many constant-time steps the program takes for an input of size n.

Answer 2

Technically, this is both, because Big O is an upper bound and everything that's O(n) is also O(n²).

But yes, this is O(n). Θ(n), in fact. (See this question for the distinction.)

Big O is not "the worst case scenario". Some algorithms can have "average case" and "worst case" time complexities that can be very different. Quick sort, for instance, is O(n log n) average case and O(n²) worst case. No one usually call quick sort an O(n²) algorithm, though.

Big O is a ceiling of how much the complexity of an algorithm grows as n increases. The complexity of an O(n) algorithm grows at most linearly. In your case, as the other answers explained, the inner loop is constant time, so the overall time complexity is a linear function of n - hence, O(n).

Answer 3

The only "handle" you have on this "algorithm" is n, and n is only used in the outer loop.

The inner loop is constant time complexity, so overall you have O(N).