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

• nir shahar: The outer loop runs $O(\log(n))$ time (alone). Then why do you think the entire code runs in less time?
• nir shahar: I think your friend's approach is correct.
• Turing101: Okay.. Thank you. :)
• ErroR: Hi, i answer your question, if it's useful for you, then accept my answer, please.

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

• nir shahar: $i$ runs from 1ドル$ to $n$ with jumps of multiplying by 2ドル$. There are a total pf $\log(n)$ such $i$'s, but they are not 1,2,ドル\dots,\log(n)$. Rather, they are 1,2,4,8,ドル\dots,n$
• ErroR: @nirshahar I edit my solution.
• nir shahar: Cool, looks good now. Its still not very intuitive to make this into a recursive formula, but the solution is correct :)
• Turing101: Thanks Rostami.. :)

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.

• Turing101: sorry, i have mistakenly written 0 in the loop, it should be 1.
• Turing101: There have been a couple of types from me.. The actual loop is for(int i=1;i<n;i=i*2){for(int j=1;j<i;j=j*2){}}
• nir shahar: This doesnt look like an answer to the OP's question...