If f(n) = Θ(g(n)) does that also mean 2^f(n) = Θ(2^f(n))?

Question

I know that if f(n) = Θ(g(n)) does that also mean g(n) = Θ(f(n))? but is it true for this case please answer me. I didn't know how to prove it i tried using the definitions but it didn't work i'm i overlooking something

Answer 1

You seem to have two distinct questions -- one in the title, regarding exponentiation, and the other in the body, regarding symmetry of the $\Theta(\cdot)$ notation.

• Question in the title: "if $f(n)=\Theta(g(n))$, do we have $2^{f(n)}=\Theta(2^{g(n)})$?"

No. Take $f(n)=n$, $g(n)=2n$. Do we have $2^{n} = \Theta(2^{2n})$?

$2^{f(n)} = 2^n$ and $2^{g(n)} = 2^{2n} = \left(2^n\right)^2 = \left(2^{f(n)}\right)^2$

• Question in the body: "if $f(n)=\Theta(g(n))$, do we have $g(n)=\Theta(f(n))$?"

Yes. Go back to the definition: $f(n)=\Theta(g(n))$ means there exists constants $a,b,N > 0$ such that for $n\geq N$ we have $a\cdot g(n) \leq f(n) \leq b\cdot g(n)$. This implies that $\frac{1}{b}\cdot f(n) \leq g(n) \leq \frac{1}{a}\cdot f(n)$ for any $n\geq N$, i.e. $g(n)=\Theta(f(n))$.