Big O notation estimate

Question

Not sure if this is the right place for this kind of question but here it goes. Given the following code, how many basic operations are there, and how many times is each one performed. What is the big O notation for this running time. This is in MATLAB, if it matters.

total = 0;

for i = 1:n
    for j = 1:n
        total = total + j;
    end
end

My thinking is that, for each n, the j = 1:n loop runs once. Within the j = 1:n loop there are n calculations. So for the j = 1:n loop its n^2. This runs n times within the i = 1:n loop, so the total amount of calcultions is n^3, and the big O noation is O(N^3). Is this correct?

Answer 1

The short answer is:

O(n^2)

The long (and simplified) answer is:

The big "O" refers to the complexity of an algorithm (in this case, your code). Your question asks "how many" loops or operations are performed, but the "O" notation gives a relative idea of the complexity of an algorithm, thus not an absolute quantity. This would totally be impractical, the idea of the O notation is to generalise a measure of the complexity so that algorithms can be compared relatively to the other, without worrying too much about how many assignments, loops, and so on are performed.

That being said, there are specific guidelines on how to compute the complexity of an algorithm. Generally:

• Loops are of complexity O("n"), not matter how many iterations they perform (remember, this is an abstract measure).
• Operations such as assignments, additions etc are generally approximated to O(1) (complexity of 1) because the time they take to be performed is negligible.

There are specific rules for if then else operations, but it would make things more complicated and I invite you to read some introduction material on performing algorithm complexity analysis.

Also, be careful, the "n" is not that used in your code, it is a special notation used to denote a "generic" linear complexity.

Measuring the complexity of an algorithm is a recursive operation. You start with the basic operations and move up to loops etc. So, here is a detailed (I purposely detail too much so you get an idea of how it works, but in practice you don't have to go in that level of detail):

You start of with the first instruction:

O(total = 0;) = O(1)

because it is an assignment.

Then:

O(total = total + j;) = O(total + j) + O(total = x)

where x is the result of total + j.

                      = O(1) + O(1)

These are basic operations, thus they have a complexity of 1.

                      = O(1)

Because "O" is a "greatness" indicator that considers any sum of constants as 1.

Now coming to the loop:

O(
    for i = 1:n // O(n)
        for j = 1:n // O(n)
            total = total + j; // O(1)
        end
    end
)
=
O(
    n * ( 
        n * (
            1
        )
)
= O(n * n * 1)
= O(n^2)

If you had two loops in a row (for ... ; for .... ;), the complexity would not be O(2n), but O(n), because again, O generalises.

Hope that helps :)

Answer 2

Your analysis is on the right track, but you're overestimating the cost by a factor of n. In particular, look here:

Within the j = 1:n loop there are n calculations. So for the j = 1:n loop its n^2.

You are right that the j = 1:n loop does n calculations, but each individual iteration of the loop only does 1 calculation. Since the loop runs n times, the work done is O(n), not O(n²). If you then repeat the rest of your analysis from that point, you'll end up getting that the total work done is Θ(n²), a tighter bound than what you had before.

As a note - you can actually speed this up pretty significantly. Notice that the inner loop adds 1 + 2 + 3 + ... + n to the total. We know that 1 + 2 + 3 + ... + n = n(n+1)/2, so you can rewrite the code as

total = 0;

for i = 1:n
     total = total + n * (n + 1) / 2;
end

But notice that now you're just adding in n copies of n * (n + 1) / 2, so you can just rewrite this as

total = n * n * (n + 1) / 2

and the whole thing takes time O(1).