Question

What is the time-complexity of the following code? Show how you derive the solution.

for(i = 1; i < 3ⁿ; i++) {

for (j = 1; j < 2ⁿ; j++ ) {

for(k = 1; k < n; k *= 2) {

m += j;

}

}

}

Answer 1

for(i = 1; i < 3^n; i++)
Values of i in this loop are 1,2,3,4,....,
So, Number of values for i = 

for(j=1; j < 2^n; j++)
Values of j in this loop are 1,2,3,4,....,
So, Number of values for j = 

for(k=1; k < n; k*=2)
Values of i in this loop are 1,2,4,8,....,n
So, Number of values for k = log(n)

Time complexity 
= O(Product of number of values for each loop variable) 
= O( log(n))