2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Do you mean $2^n+1$ or $2^{n+1}$? See math notation guide. $\endgroup$
    – user147263
    Mar 7, 2015 at 19:47
  • $\begingroup$ I can't seem to get it to format correctly but its, f(n) = 2^(n+1) = Θ(2^n) $\endgroup$
    – John
    Mar 7, 2015 at 19:51
  • $\begingroup$ Include the exponent in braces like $2^{n+1}$. $\endgroup$
    – quid
    Mar 7, 2015 at 19:57

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

An other way to see it, is to find the limit

$$\lim_{n \to +\infty} \frac{2^{n+1}}{2^n}=\lim_{n \to +\infty} \frac{2^n \cdot 2}{2^n}=\lim_{n \to +\infty} 2=2$$

It is known that if $\lim_{n \to +\infty} \frac{f(n)}{g(n)}=c \in \mathbb{R}$ then $f(n)=\Theta(g(n))$.

$\endgroup$
1
  • $\begingroup$ Provided he really means $n \to \infty$, which he didn't say. I'm guessing (as you did) that this is what he means. $\endgroup$
    – GEdgar
    Mar 7, 2015 at 20:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .