Big-O Notation for Nested Loops Explained

algorithmsbig ocomplexityperformance

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?

Best Answer

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(n2 ).

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(nk ).

Related Topic