3 nested for loops complexity

EladAskenazi
int x = 0;
for (int i = n; i >= 3; i--) {
    for (int j = 1; j <= Math.log(i) / Math.log(2); j++) {
        for (int t = 0; t <= n; t += j) {
            x++;
        }
    }
}
System.out.println(x);

As you can see I have 3 for loops whose conditions depend on each other.

My analysis:

  • The first loop: I assumed that it will run (n-2) times "worst case" scenario.
  • The second loop: I assumed it will run log(n) times "worst case" scenario.
  • The third loop: I assumed it will run (n) times "worst case" scenario.

So I have calculated that the function of the 3 loops will be: (n-2)*(log(n))*(n)=(n^2)*log(n)-(2n)*log(n) = O((n^2)*log(n))

I'm not sure that my calculation is correct, please do advise!

meowgoesthedog

One must be careful when dealing with multiple nested loops whose conditions depend on each other. Simply multiplying their individual complexities may lead to the wrong result.


  • Inner loop

    This runs approximately n / j times. The precise value is floor([n + 1] / j).

  • Middle loop

    This runs approximately log2(i) times. The precise range of j is [0, floor(log2(i))].

  • Outer loop

    This can be reversed without affecting the time complexity, i.e. (int i = 3; i <= n; i++)

Combining the above into a summation:

enter image description here


Math notes:

  • A number rounded down only differs from its original value by less 1, i.e.:

    enter image description here

  • The summation of 1 / j is the Harmonic Series, the asymptotic expression for which is:

    enter image description here

  • Stirling's approximation: log(n) + log(n-1) + log(n-2) + log(n-3) + ... = O(n log n)

Applying the above:

enter image description here


Thus:

enter image description here

What is the asymptotic complexity of the inner product expression –

log(3) * log(4) * log(5) * ... * log(n) ?

The upper bound is given by log(n) raised to the power of the number of terms, i.e. log(n)^(n-2):

enter image description here

Which is different to the result obtained by directly multiplying the worst case complexities O(n^2 log n).

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related