CODEWITHSUNDEEP
algorithmtime-complexitybig-ocomplexity-theory
Lazlow
Lazlow

Reputation: 73

Time complexity of three nested loops?

What the time complexity of the code

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

The first 2 loops create a O(n^2) right ?

At the third loop "int k=1" executes 1 time,

what about k

k*=2

and count++

with other words whats the time complexity of the third loop ?

Upvotes: 0

Views: 2246

Answers (2)

dfrib
dfrib

Reputation: 73176

If you want to analyze your algorithm thoroughly, you can use Sigma notation to analyze the number of times count++; executes

enter image description here

Hence, your algorithm runs in O(n^2 · log n).

Note: equality (*) holds for all values of n that are not a multiple of 2 (n%2 != 0). In cases where n is a multiple of 2 (n%2 = 0), simply remove the floor function in the sum and subsequent expressions following equality (*) above.

Now, from the above, we realize that the expression of T(n) as specified just prior to the less or equal to symbol (≤) above will yield the exact value of count after the loops (given that count=0 prior to loops), without implicitly needing to execute the nested loops.

T(n) = n^2*(1 + floor(log(n)/log(2))), if n%2 != 0,
       n^2*(1 + log(n)/log(2)),        if n%2  = 0.

This can be useful in cases where you have an algorithm that simply just counts something; instead of explicitly performing the loops to execute such a tedious (and, for large values of n, slow) counting task, you can derive your own formula for the number of counts, much like above, and use in your program instead.

We can verify the formula derived for this case correctly calculates the actual iteration count:

//        count                 count
// n      (after triple loop)   (by T(n) formula)
// ----   -------------------   -----------------
// 10     400                   400
// 100    70 000                70 000
// 1000   10 000 000            10 000 000

Upvotes: 1

recursive
recursive

Reputation: 86064

The inner loop is O(log n) since the "increment" step is actually a multiplication.

That means the entire algorithm is O(n^2 log n).

count++; executes in constant time, so it doesn't contribute anything to big O analysis.

Upvotes: 4

Related Questions