for (int i = 0; i < n / 2   1; i  ) {
    for (int j = i; j < n; j  ) {
    }
}

What complexity would it be for this example and what is the quick calculation for knowing that? n is the array length.

CodePudding user response：

Count the number of iterations you do.

• In the first pass of the outer loop you do n cycles of the inner loop
• The second is n - 1
• this continues on until the outer loop i is n / 2 and the inner cycles n - n/2 times.

Thus the total number of iterations is: n n - 1 .. n - n/2 = n * (n/2 1) - (n/2) * (n/2 1)/2 = 3 * n * n/8 3 * n/4

Thus the complexity function is 3*n*n/8 3*n/4, which is member of O(n^2) (also tetha(n^2))

EDIT: In the calculations I do I use the formula 1 2 3 .. n = n*(n 1)/2, which, at least to me is something I know by heart, but is inferred as a formula by Gauss.

CodePudding user response：

I think the easiest way to explain it is like following:

The outer loop runs nearly half of n times, and for at least n/2 of those iterations, the inner loop runs at least n times. The total number of inner loop iterations is therefore at least n * n/2 and That's O(n^2)

CodePudding user response：

When you double n, the amount of iterations goes times 4.
When you triple n, the amount of iterations goes times 9.
...

=> the complexity is O(n^2).

CodePudding user response：

The other answers are not wrong, but if you compiled this and tried to measure the execution time for different values of n, it is possible that you would get the same result regardless of the value of n.

This is because, depending on the optimization settings, the compiler may recognize that nothing happens in these loops which has any effect after they are completed. Thus the loops may be optimized away entirely. See e.g. https://godbolt.org/z/bc9Mzr7db.