3 nested for loops complexity

Question

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!

Answer 1

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:

---

Math notes:

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

  

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

  

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

Applying the above:

---

Thus:

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

Which is a tighter bound than the result obtained by directly multiplying the worst case complexities of each loop, O(n^2 log n).