Algorithmic complexity o (n)

Question

I recently started playing with algorithms from this princeton course, and I noticed 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 general pattern here is that as nesting in the cycle increases, the exponent also increases. Can I assume that if I have a 20-cycle, my complexity will be 0 (N ^ 20)?

PS: Please note that 20 is just a random number that I chose, and yes, if you put 20 loops in your code, something is wrong with you.

Answer 1

It depends on what the loops do. For example, if I changed the end of the second loop by simply doing 3 iterations as follows:

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

back to O (N)

---

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

---

Here is another example where the second cycle goes into N ^ 2:

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

It will be o (N ^ 3)

Answer 2

Yes, if the loop length is proportional to N , and the loops are nested into each other, as you described.

Answer 3

In your specific template, yes. But it is unsafe to assume that in general. You need to check if the number of iterations in each cycle is O (n), regardless of the state of all closed cycles. Only after you confirm that it is, can you conclude that complexity is O (n ^{loop-nesting-level} ).

Answer 4

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

Answer 5

I highly recommend that you understand why a double nested loop with every loop going from 0 to N equals O (N ^ 2). Use summation to estimate the number of steps involved in for loops, and then reset the constants and reduce you will get Big-Oh of this algorithm.