How to find the number of operations in a nested loop with dependent variable?

Question

I am having difficulty trying to find the total number of operations in the following code block:

for(int i = 1; i <= n; i *= 2) {
   for(int j = 1; j <= i; j *= 2) {
       // What is the number of operations here, with respect to n?
   }
}

My thinking was that: there are floor(log_2(n)) operations in the outer loop, and log_2(i) operations in the inner loop. I am not sure if my thinking is right, and how I would go from here... How could this be written in terms of solely n?

Answer 1

As you said, there are floor(log_2(n)) operations in the outer loop. For simplicity let's say log_2(n) operations. It won't matter so much for the large number of inputs. In the inner loop, number of operations will be log_2(i) for each case.
So, from i=1 to i=n, number of inner loop operations:

A = log_2(1)+1 (i = 1) + log_2(2)+1 (i = 2) + log_2(4)+1 (i = 4) + ... + log_2(n)+1 (i = n)
A =  1 + 2 + 3 + ... log_2(n) + 1
A = (log_2(n) + 2) * (log_2(n)+1) / 2 
A = ((log_2(n))^2 + 3*log_2(n) + 2)/2

Total number of operations = (log(n)^2 + 3log(n) + 2)/2
In short, time complexity of the algorithm will be : O(log(n)^2)