Clarrification on quadratic running time

Question

I have code like this:

for (int i = 0; i <= n; i++)
{
    for (int j = 0; j <= i; j++)
    {
        f(); // constant operation
    }
}

The number of times f would execute appear to be:

n+n+(n-1)+(n-2)+(n-3)+...+2+1+0 = (n*n)-n = n^2-n

If we drop the low-order term (-n), The big O would be O(n^2).

Is this all correct?

@hnefatl I edited the code, it should be i <= n. n+n is not a typo. — lightning_missile, Jan 21 '18 at 16:20
@morbidCode Then it should be `(n+1) + n + (n-1) + ...`, no? — hnefatl, Jan 21 '18 at 16:20
@morbidCode There are `n+1` distinct values in between `0` and `n` inclusive, and when `i = n`, `j` will go from `0` to `n` inclusive. — hnefatl, Jan 21 '18 at 16:25
@hnefatl yes you're right! Thanks! Maybe you can put that as an answer? — lightning_missile, Jan 21 '18 at 16:27

score 0 · Accepted Answer · answered Jan 21 '18 at 16:31

Your derived complexity is correct, but there are two errors in your equation for the number of times the loops run for:

for (int i = 0; i <= n; i++)
{
    for (int j = 0; j <= i; j++)
    {
        f(); // constant operation
    }
}

There are n + 1 distinct values in the inclusive range 0 to n, so your inner loop will run for i + 1 iterations. As such, your formula should be:

(n + 1) + n + (n - 1) + ... + 1 + 0 = n(n + 1)/2 = (n^2 + n)/2

As it's an arithmetic series. This is still O(n^2), as n^2 grows faster than n and the constant 1/2 doesn't matter.

Clarrification on quadratic running time

1 Answers1