Growth order for cycles

Question

What will be the order of code growth below. I assumed that each cycle growth is linear, but the if statement confuses me. How do I incorporate this with all of this. I would really appreciate an explanatory answer to understand the process.

int count = 0; 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) count++; 

Answer 1

When trying to determine the complexity of a code, two things can be confusing.

• The fact that not all cycles start at 0. The second cycle starts at i + 1 , and the third starts at j + 1 . Does it affect complexity? Is not. Consider only the first two loops. For i = 0 second is executed N - 1 times, for i = 1 , N - 2 times, ..., for i = N - 1 , 0 times are executed. Add it all:

   0 + 1 + ... + N - 1 = N(N - 1) / 2 = O(N^2). 

  Thus, not starting at 0 does not affect complexity (remember that big-oh ignores lower order terms and constants). Therefore, even with this setting, all this is O(N^3) .

• if The if obviously does not matter here because it is only part of the last loop and does not contain a break statement or other code that affects the loops. This affects only the increase in the counter, and not on the execution of any of the cycles, so we can safely ignore it. Even if the counter does not increase (operation O(1) ), the if condition is checked (also operation O(1) ), therefore the same crude number of operations are performed using and without if .

  Therefore, even with the help of the if algorithm is still O(N^3) .

Answer 2

The order of code growth will be O (N ^ 3).

In the general case, nested loops of length N contribute to the growth of O (N ^ k).

Answer 3

Here two of them were to find that the time complexity is Theta (N ^ 3) without much calculation.

First you select i<j<k in the range from 0 to N-1. The number of ways to select 3 objects from N is a binomial coefficient N choose 3 = N*(N-1)*(N-2)/(3*2*1) ~ (N^3)/6 = O(N^3) , or rather, Theta (N ^ 3).

Secondly, the upper bound is that you choose i, j and k from N possibilities, therefore there are no more than N*N*N = N^3 options. This is O (N ^ 3). You can also find the lower bound of the same type, since you can choose i from 0 to N / 3-1, j from N / 3 to 2N / 3-1 and k from 2N / 3 to N-1. This gives you at least a gender (N / 3) ^ 3 of choice, which is about N ^ 3/27. Since you have an upper bound and a lower bound of the same kind, the time complexity is Theta (N ^ 3).