I have a problem were I need to prove big theta. $f(n) = 2^{n+1} = Θ(2^n)$. I proved that this was true for big O but I'm not sure how to go about proving big Theta.
[Math] How to prove that $2^{n+1} = \Theta(2^n)$
asymptotics
asymptotics
I have a problem were I need to prove big theta. $f(n) = 2^{n+1} = Θ(2^n)$. I proved that this was true for big O but I'm not sure how to go about proving big Theta.
Best Answer
You need to show that there are positive constants $c_1,c_2$ such that
$$c_1 2^n \le 2^{n + 1} \le c_2 2^n$$ for all [sufficiently large] $n$.
For the $O$ you already found the second. The first is rather easier, so I am confident you will make it with this info at hand.