-3

I don't understand why the time complexity of the following algorithm is O(N^2) and not O(N*i)...?

for (int i = 0; i < N; i++)
{
    a[i] *= 2;
    for (int j = 0; j < i; j++)
        d[i][j] = a[i] * c[j];
}

I would greatly appreciate it if someone would be able to point me in the right direction...

1
  • 2
    i is not a free parameter but a loop variable. What should O(N*i) complexity mean?
    – Evg
    Jun 4 at 1:45

2 Answers 2

2

It does not matter if a nested loop does not iterate the same amount of a outer loop. The overall time complexity is O(N^2).

C = O(N) + O(0 + 1 + 2 + ... + N - 1)

O(N) is a[i] *= 2, the right part is the inner loop. This is a sum of the arithmetic mean progression:

C = O(N) + O(N * (N - 1) / 2) = O(N) + O(N^2/2 - N/2) = O(N) + O(N^2) + O(N^2)
1

Because here the loops are simple, it's easy to count all actions done.

The a[i] *= 2 is done N times.
The d[i][j] = a[i] * c[j] is done:

  • when i==0 : 0 times
  • when i==1 : 1 times
  • ...
  • when i==N-1 : N-1 times.
    The total is: N + 0 + 1 + ... + N-1 = N + (N-1)(N-2)/2 = (1/2)(N^2) - N/2 + 1.

For O() we consider only the highest power and ignore constant coefficients, here it is O(N^2).

Why this? We want to know what happens when N is big.
E.g: N = 1,000 => exact number is (1/2)(N^2) - N/2 + 1 = 499,501.
N = 10,000 => exact number is (1/2)(N^2) - N/2 + 1 = 49,995,001.
We see that for N 10 times bigger, result is about 100 times bigger. It is O(N^2).

We can do shorter, rereading the code:
There is a loop on N, and inside a loop limited by i and i is varying like N. It is a O(N^2) process.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.