1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ The outer loop runs $O(\log(n))$ time (alone). Then why do you think the entire code runs in less time? $\endgroup$ – nir shahar Jun 14 at 10:22
  • $\begingroup$ I think your friend's approach is correct. $\endgroup$ – nir shahar Jun 14 at 10:23
  • $\begingroup$ Okay.. Thank you. :) $\endgroup$ – Turing101 Jun 14 at 10:34
  • $\begingroup$ Hi, i answer your question, if it's useful for you, then accept my answer, please. $\endgroup$ – Rostami.M Jul 18 at 14:04
6
$\begingroup$

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

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

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

$\endgroup$
-1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.