Big-O for nested loop

Question

I am reading this post on Big-O
It says that the following code is O(n^2):

bool ContainsDuplicates(String[] strings)
{
    for(int i = 0; i < strings.Length; i++)
    {
        for(int j = 0; j < strings.Length; j++)
        {
            if(i == j) // Don't compare with self
            {
                continue;
            }

            if(strings[i] == strings[j])
            {
                return true;
            }
        }
    }
    return false;
}

But I can not understand why.
The inner loop does something constant.
So it is summation of 1....N of a constant. i.e. constant number O(1).
The outer loop is summation over the O(1).
So I would imagine it is n*O(1).

I think I am misunderstanding something here.
I do not think that all nested loops mean O(n^2), right?

Answer 1

Your mistake is with the inner loop. It does something constant n times, so it is O(n). The outer loop does the inner loop n times, so it is O(n × n), or O(n² ).

In general, if the number of iterations a loop makes is dependant on the size of the input, it is O(n). And if k such loops are nested, it is O(n^k ).

Answer 2

If the length of the string is n, the test if i == j will execute n^2 times. The order of an algorithm is the order of whatever part of it has the highest order. Since 'i' is compared to 'j' n^2 times, the order of the algorithm cannot possibly be less than O(n^2).

For a very large 'n', doubling 'n' will quadruple the run time.

Answer 3

You are misinterpreting what a constant operation means.

A constant operation is an operation which always executes in fixed amount of time independent of input it receives.

i == j is a constant operation because it executes this statement in fixed amount of time. Lets say it takes 1 unit of time.

But this constant operation is performed (no of values of i)*(no of values of j) times. Lets say i and j are run 10 times each. Then by calculation it takes 100 unit of time for completion of i==j when in a nested loop. So it will vary as the values of i and j vary.

We can be sure that i==j will be done in 1 unit time but we cannot know how many times i==j will be performed.

If it is performed n times then it will take n units of time. Outer loop executes inner loop n times. So in essence i==j operations is done n^2 times.

All nested loops mean O(n^(no of nested loops)). Here O means the upper limit which means code will execute in less than or equal to the value of O(). This is the guarantee that it will not take longer than that but it can take less time not larger.

Answer 4

Nested loops run O(i₁ * i₂ * ... * i_n), where n is the number of nested loops and i_x is the number of iterations in loop x. (Or, to put that another way, it's the product of the number of iterations in each of the loops.)

Your pair of loops iterates over the same array twice, which by coincidence is O(n * n) or O(n²).

What happens inside the innermost loop is treated as constant because it's going to happen every time. Big-O notation isn't really about measuring the performance of linear code, it's more about making relative comparisons of how iterative algorithms behave when given n items of input to deal with. Certain operations that don't actually do any iterating (such as a push or pop on a stack) get dinged as O(1) because they do handle one element of the data.