Find the time complexity of the following snippet?

Question

For(i=1;i<(1<<n);i++)
{
Do something
}

What is the meaning of the expression in the condition part of the for loop?

Comments

Are you sure the question is properly frammed ?

---

This is the question from the study material provided Gateforum. According to them, 2^n is the answer.

And this is the solution they havr provided!

Answer 1

$\lt\lt$ is Left Shift operator.

 100(4 in decimal) << 1 == 1000 (8)( which is equivalent to multiplying by 2) 
 1 << 2 == 100 (4 in decimal)

So, $1 \lt\lt n$ means $1$ is being shifted by $n$ bit positions.

$\large \color{green}{ 1 \lt\lt n  = 2^{n}}$

Index $i$ starts with $ i = 1 $ and goes till $ i \lt 2^{n} $. So, total no. of times loop executes is $2^{n}-1$

So, Time complexity of Above code is :  $ O(2^n) $

Comments

You explained n << 1 and then solved 1 << n .you  Need to correct it

---

thanks for pointing it out

Answer 2

I have modified your code for better undrstanding

  #include <stdio.h>
    int main()
    {
 	    int i,c=0 ,n=8;                              //const time say (a )
		for(i=1;i<=(1<< n);i++)
		{
    	c=c+1;  
		}

		printf("\n %d ",c );
    }

Here , Time complexity is nothing but home many times the loop gets executed . 
 

 1 << n

This means that 1 is being left shifted 'n' bit positions .

that ie  1 << 3 $\Rightarrow$  0000 0001 left shifted 3 bit positions 0000 1000 becomes 8 it is nothing but $2^{3}$

Now, lets get back to our problem ,

for i= 1  loop gets executed $2^{1} - 1$ $\Rightarrow$ 2-1 time
for i= 2  loop gets executed $2^{2} - 1$ $\Rightarrow$ 4-1 time
for i= 3  loop gets executed $2^{3} - 1$ $\Rightarrow$ 8-1 time
for i= n  loop gets executed $2^{n} - 1$ $\Rightarrow$ 2ⁿ-1 time

Therefore Time Complexity of the code is $\Theta(2^{n})$