Why $2^n$ is $\Theta (2^{n+1})$?
1,767
To show that $2^n$ is in $\Theta(2^{n+1})$, you need to show that there exists constants $c_1,c_2$ such that $$c_1\cdot 2^{n+1} \leq 2^{n}\leq c_2\cdot 2^{n+1}$$ holds for all sufficiently large $n$.
Hint: $$2^{n+1} = 2\cdot 2^n.$$ Now find constants $c_1,c_2$ such that it holds.
Related videos on Youtube
Author by
Rain
Updated on February 23, 2020Comments
-
Rain over 3 years
Why $2^n$ is $\Theta (2^{n+1})$? I have come across any example saying
“It is easy to see that $2^n$ is $\Theta(2^{n+1})$. That is an example of many functions that satisfy $f(n)= \Theta(f(n+1))$.”
Why is that true? And what are these functions which satisfy $f (n)= \Theta(f(n+1))$ ?
I would really appreciate any help. Thanks in advance
-
Parcly Taxel over 6 yearsThe relevant constants that show $2^n=\Theta(2^{n+1})$ are $c_1=\frac14$ and $c_2=1$.
-
Dean C Wills over 6 years@parcly-taxel is correct. Essentially, when you find a question like this, you want to refer to the definitions of each of the terms and see if you can prove it.
-
kingW3 over 6 yearsBecause $2^{n+1}=2\cdot 2^n$ and $2$ is a constant.
-
Did over 6 years@ParclyTaxel Or $c_1=c_2=\frac12$.
-