Prove that Prove that 4n NotElement theta 2nSolutionlet fn

Prove that

Solution

let f(n) = 4^n

f(n) = 2^(2*n)

f(n)= 2^(2n)

which is equal to thetaof(2^2n)

and right hand side is thetaof(2^n);

Clearly left hand side i.e 4^n or 2^2n grows faster than 2^n, hence they are not equal to each other.