Algorithmic complexity of o(n)

Question

I recently started playing with algorithms from this princeton course and I observed the following pattern

O(N)

 double max = a[0];
  for (int i = 1; i < N; i++)
     if (a[i] > max) max = a[i];

O(N^2)

for (int i = 0; i < N; i++)
     for (int j = i+1; j < N; j++)
        if (a[i] + a[j] == 0)
           cnt++;

O(N^3)

for (int i = 0; i < N; i++)
     for (int j = i+1; j < N; j++)
        for (int k = j+1; k < N; k++)
           if (a[i] + a[j] + a[k] == 0)
cnt++;

The common pattern here is that as the nesting in the loop grows the exponent also increases. Is it safe to assume that if I have 20-for loops my complexity would be 0(N^20)?

PS: Note that 20 is just a random number I picked, and yes if you nest 20 for loops in your code there is clearly something wrong with you.

Answer 1

It depends on what the loops do. For example, if I change the end of the 2nd loop to just do 3 iterations like this:

for (int i = 0; i < N; i++)
    for (int j = i; j < i+3; j++)
       if (a[i] + a[j] == 0)
          cnt++;

we get back to O(N)

---

The key is whether the number of iterations in the loop is related to N and increases linearly as N does.

---

Here is another example where the 2nd loop goes to N ^ 2:

for (int i = 0; i < N; i++)
    for (int j = i; j < N*N; j++)
       if (a[i] + a[j] == 0)
          cnt++;

This would be o(N^3)