for ( int i = 1; i < n*n*n; i *= n ) {
    for ( int j = 0; j < n; j  = 2 ) { 
        for ( int k = 1; k < n; k *= 3 ) { 
            cout<<k*n;
        }
    }
}

I am facing an issue with this exercise, where I need to find the big O notation of the following code, but I got O(n^5) where the first loop is n^3, 2nd loop n, and the 3rd loop is n and I am not sure if I am correct or not. Can someone help me please?

CodePudding user response：

First loop is i=1 and every time multiplies by n until its n^3 so its 3 times, which is O(1).
Second loop is j=1 and every time added 2 until its n so its n/2 times, which is O(n).
Third loop is k=1 and multiplies by 3 until its n, which is O(log(n))
Overall: O(n*log(n))

CodePudding user response：

Your analysis is not correct.

The outer loop multiplies i by n each ietration,starting from 1 till n^3.
Therefore there will be 3 iterations which is O(1).

The middle loop increments j by 2 each iteration, starting from 0 till n.
Therefore there will be n/2 iterations which is O(n).

The inner loop multiplies k by 3, from 1 till n.
Therefore there will be log3(n) iterations, which is O(log(n)).
If this step is not clear, see here: Big O confusion: log2(N) vs log3(N).

The overall time complexity of the code is a multiplication of all the 3 expressions above (since these are nested loops).
Therefore is it: O(1) * O(n) * O(log(n)), i.e.: O(n*log(n)).

CodePudding user response：

You are not correct. In first loop for ( int i = 1; i < n*n*n; i *= n ) pay attention to "statement 3"(i *= n), and in third loop for ( int k = 1; k < n; k *= 3 ) also pay attention to "statement 3"(k *= 3). Your calculation for second loop is great.