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.

Share:
1,767

Related videos on Youtube

Rain
Author by

Rain

Updated on February 23, 2020

Comments

  • Rain
    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
      Parcly Taxel over 6 years
      The relevant constants that show $2^n=\Theta(2^{n+1})$ are $c_1=\frac14$ and $c_2=1$.
    • Dean C Wills
      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
      kingW3 over 6 years
      Because $2^{n+1}=2\cdot 2^n$ and $2$ is a constant.
    • Did
      Did over 6 years
      @ParclyTaxel Or $c_1=c_2=\frac12$.