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.

Think of it like this: what controls the number of iterations? Is it the size of `N`? If all loops change linearly with `N` then yes, you get N^x where x is the number of nested loops. — keyser, Aug 13 '13 at 17:34
Have a look at this:- http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it. — Vedant Terkar, Aug 13 '13 at 17:36

score 6 · Accepted Answer · answered Aug 13 '13 at 17:36

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)

I think this answer was very well explained. – Ivan Aug 13 '13 at 17:59 — Ivan, Aug 13 '13 at 17:59

score 2 · Answer 2 · edited Aug 13 '13 at 17:36

2

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

edited Aug 13 '13 at 17:36

keyser

18,829
16
59
101

answered Aug 13 '13 at 17:35

FrankPl

13,205
2
14
40

score 1 · Answer 3 · answered Aug 13 '13 at 17:35

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}).

user · Answer 4 · 2013-08-13T17:41:17.437

0

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)

edited Aug 13 '13 at 17:41

answered Aug 13 '13 at 17:33

user

719
8
17

score 0 · Answer 5 · answered Aug 13 '13 at 17:41

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.

Algorithmic complexity of o(n)

5 Answers5