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)

Answer 2

Yes, if the length of the loop is proportional to N and the loops are nested within each other like you described.

Answer 3

In your specific pattern, yes. But it is not safe to assume that in general. You need to check whether the number of iterations in each loop is O(n) regardless of the state of all the enclosing loops. Only after you have verified that this is the case can you conclude that the complexity is O(n^{loop-nesting-level}).

Answer 4

Yes. Even though you decrease the interval of iteration, Big-o notation works with N increasing towards infinity and as all your loops' lengths grow proportional to N, it is true that such an algorithm would have time complexity O(N^20)

Answer 5

I strongly recommend that you understand why a doubly nested loop with each loop running from 0 to N is O(N^2).Use summations to evaluate the number of steps involved in the for loops, and then dropping constants and lower order terms, you will get the Big-Oh of that algorithm.