# Time Complexity of Logarithmic For loop

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

• The outer loop runs $O(\log(n))$ time (alone). Then why do you think the entire code runs in less time? Jun 14 at 10:22
• I think your friend's approach is correct. Jun 14 at 10:23
• Okay.. Thank you. :) Jun 14 at 10:34
– Jut
Jul 18 at 14:04

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

• $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$ Jun 14 at 12:29
• @nirshahar I edit my solution.
– Jut
Jun 14 at 12:33
• Cool, looks good now. Its still not very intuitive to make this into a recursive formula, but the solution is correct :) Jun 14 at 12:35
• Thanks Rostami.. :) Jul 20 at 19:04

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

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.

• sorry, i have mistakenly written 0 in the loop, it should be 1. Jun 14 at 10:43
• 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){}} Jun 14 at 10:48
• This doesnt look like an answer to the OP's question... Jun 14 at 12:30