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!

If you don't know whether or not your calculation is correct, then you do not (yet) have a Stack Overflow question. Most important, what happened when you ran the program with various values of `n`? How did the printed values of `x` react? See [here](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Prune, Mar 20 '19 at 16:53
Well ok I see.. didn't mean to bother you in anyway that you have me a -1.. anyhow if this is the case and my question is not "stack overflow" question, would you please direct me to the right forum? @Prune — EladAskenazi, Mar 21 '19 at 09:35

meowgoesthedog · Accepted Answer · 2022-07-06T14:43:11.180

4

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

edited Jul 06 '22 at 14:43

answered Mar 20 '19 at 14:33

meowgoesthedog

14,670
4
27
40

Thank you for that, I had a bit of a hard time going over it and fully understand the concept but I got it. – EladAskenazi Mar 21 '19 at 09:31
https://stackoverflow.com/questions/55250120/how-to-calculate-the-complexity-of-a-given-code/55250962?noredirect=1#comment97264711_55250962 @meowgoesthedog is it possible to help me with that also? – EladAskenazi Mar 21 '19 at 14:55
@OmerAskes I believe `Danielle`'s answer on that page is correct and offers sufficient proof. – meowgoesthedog Mar 21 '19 at 15:01
the code seems to be very good but I would like to see an answer like yours, using math and prof the complexity of the giving algorithm. if it's possible you would sure love to see your answer or notes on the way I've solved it. @meowgoesthedog – EladAskenazi Mar 21 '19 at 16:01

3 nested for loops complexity

1 Answers1