CODEWITHSUNDEEP
c++algorithmtimebig-o
Q_i99i
Q_i99i

Reputation: 13

Big O notation calculation for nested loop

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?

Upvotes: 0

Views: 254

Answers (3)

wohlstad
wohlstad

Reputation: 28074

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

Upvotes: 1

DimitrijeCiric
DimitrijeCiric

Reputation: 446

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.

Upvotes: 0

Ofirfr
Ofirfr

Reputation: 133

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

Upvotes: 1

Related Questions