CODEWITHSUNDEEP
javactime-complexity
Yarin Mosez
Yarin Mosez

Reputation: 15

What would be the complexity of these 2 simple for loops

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.

Upvotes: 0

Views: 103

Answers (4)

nielsen
nielsen

Reputation: 7594

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.

Upvotes: 0

Boris Strandjev
Boris Strandjev

Reputation: 46943

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.

Upvotes: 4

Dominique
Dominique

Reputation: 17493

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

Upvotes: 1

raiyan22
raiyan22

Reputation: 1169

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)

Upvotes: 2

Related Questions