Time Complexity of Logarithmic For loop

Question

Say I have a for loop like this

for(int i=1;i<n;i=i*2)
{
    for(int j=1;j<i;j=j*2)
    {
         cout<<"hello";
    }
}

What is the time complexity of this loop?

I have approached this problem like this. The outer loop runs log(n) times and the inner loop runs log(i) times, so in total the complexity becomes $O(log(log(n)))$

Whereas, my friend has approached it like this. The outer loop is running,

$i=2^0$+$2^1$+$2^2$+$2^3$.... $2^{log(n)}$

times and since the inner loop is running log(i) times, so the total time complexity we have is

$TC=0+1+2+3...log(n)= O( (log(n))^2 )$

Which of these two is correct $O(log(log(n)))$ or $O( (log(n))^2 )$ ?

Answer 1

Our approach is to finding a recursive formula for the time complexity of the code. For each value of $i$, the inner loop runs $\log i$ times.

Suppose $T(n)$ is time complexity of given code, so: $$T(n)=T(\frac{n}{2})+\log n$$.

At each step we have a $\log i$ cost for inner loop, and outer loop divide our $n$ by $2$. So we get above $T(n)$ that after solving by any known method (suppose $n=2^k$): $$T(n)=\sum_{i=1}^{\log n}\log\frac{n}{2^i}$$ $$=\sum_{i=1}^{\log n}(\log n-i)=\sum_{i=1}^{\log n}i=O(\log^2n)$$ As a result: $$T(n)=O(\log^2n)$$

Answer 2

When you are working on loops like these you can simplify them with sums to count the number of iterations:
For example the time it takes on this loop

for(int i=1;i<n;i=i*2)
{ 
   cout<<"hello";
}

Can be rewritten as $\sum_{i=1}^{\log(n)}{c}$, where $c$ is the constant time for printing "hello".
Hence your double loop can be rewritten as $$\sum_{i=1}^{\log_2(n)}{\sum_{j=1}^{\log_2(2^i)}{c}} = \sum_{i=1}^{\log_2(n)}{ci} = \frac{c}{2}\log_2(n)(\log_2(n)+1) = O(\log_2^2(n))$$

Answer 3

What this code does and what you think it does are not the same thing.

The outer loop doesn't iterate at all if n <= 0, and runs forever if n > 0. The inner loop will never iterate at all. That's all because i and j will be zero forever.

If you start the loops with i = 1, j = 1, then the code still doesn't do what you think it does, and if n >= 3 then the inner loop will run forever when it's run the second time, since j never gets a value different from 1.