Doubt Algorithms Gate 2003

Question

2^2n =O(2^n)  True or False

Its false but why

Comments

$2^{2n}$ is equivalent to $4^n$ and hence is $O(4^n)$ and not $O(2^n)$

---

Thanks

Answer 1

its false....say F1=2^2n and F2=2^n

take log on both function we get

F1=2n*log(2) F2=n*log(2).....as (log 2=1..)

we get F1=2n and F2=n.......putting large values for n=1024...

F1=2048 and F2=1024......

means F1 is asymptotically larger than F2...

so given statement is false.

Answer 2

2^(2n)=O(2^n) is false.

Explanation: We know 

L.H.S= 2^(2n)

         = 2^(n+n)

         =2^n * 2^n

R.H.S= 2^n

Dividing both side by 2^n:

=> 2^n * 2^n=x(2^n)

=> 2^n = x(1)

x is definitely Ώ i.e. small omega.

So, statement: 2^(2n)=O(2^n) is false.