Finding if a f(n) is in theta of g(n)

35 Views Asked by At

$$2^{3^n}\in Θ\left(2^{3^{n+1}}\right) $$

My intuition about it was to disregard constants since we are talking about asymptotic analysis. $ 2^{3^{n+1}} $ can be rewritten as $2^{3\cdot 3^n}$ which is equal to $8^{3^n}$ and since 2 and 8 are constants it follows that they are asymptotically equal and the answer to the question is true?

1

There are 1 best solutions below

0
On

$$ 2^{3^n}\in \Theta\left(2^{3^{n+1}}\right) $$means, among other things, that you can find a constant $k$ such that $k\cdot 2^{3^n}$ is larger than $$2^{3\cdot 3^n}=\left(2^{3^n}\right)^3=2^{3^n}\cdot2^{3^n}\cdot2^{3^n}$$for all large $n$. That's quite clearly not possible. Instead, we have $$ 2^{3^n}\in o\left(2^{3^{n+1}}\right) $$ The base of a power expression with a variable in the exponent is in no way just a constant. So your $2$ and $8$ give significantly different asymptotics.