Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I understand the main idea of big-O-notation, yet I have two questions regarding to the following examples:

Prove/Disprove:
1. $2^{2n+1} = O(2^{2n})$
2. $2^n = O(2^{n\over 2})$

Questions:

  1. I looked at the proof showing that the expression equivalent to: $2\cdot 4^n + 3^n = O(4^n)$. Where did the $3^n$ came from?

  2. I understood that this statement is false, so lets assume by contradiction it's true that: ${2^n} \le c \cdot {2^{\frac{n}{2}}}$ for all $n\ge n_0$. What should I do next? dividing by ${2^{\frac{n}{2}}}$ brought me an odd result.

Thanks.

share|improve this question
1  
1. There is no $3^n$, it's definitely a typo. 2. In this "odd result", what happens if you let $n \to \infty$? –  Antonio Vargas Mar 9 at 14:32
    
For 2., you dividing should give you $2^{n/2} \leq c$. Is that what you got? –  Darren Naylor Mar 9 at 14:41

2 Answers 2

up vote 1 down vote accepted
  1. $2^{2n+1} = 2\cdot 2^{2n}$. Since you always have $f(x) = O\left(f(x)\right)$ and since $f(x) = O\left(g(x)\right)$ implies $c\cdot f(x) = O\left(g(x)\right)$, it follows that $2^{2n+1} = O(2^{2n})$.

  2. If $2^n = O\left(2^{\frac{n}{2}}\right)$, then there is a $c$ and an $n_0$ such that for all $n \geq n_0$ you have $2^n \leq c\cdot 2^{\frac{n}{2}}$. (You wrote $n < n_0$, I assume that is a typo). Dividing by $2^{\frac{n}{2}}$ makes this $2^{\frac{n}{2}} \leq c$, and taking the logarithmn plus some rearranging gives $$ n \leq 2\log_2 c \text{.} $$ for all $n$ larger than some $n_0$. That can't be true - whatever you pick for $c$, the right side yields some finite value, so there's always an $n$ larger than that value.

share|improve this answer
    
Great, thank you sir! –  AnnieOK Mar 9 at 14:55
1  
@AnnieOK BTW, $f(x) = O\left(g(x)\right)$ can be a bit of a treacherous notation. You won't be able to get around that notation - it's used very wildely - but I suggest that you think of it rather as $f(x) \in O\left(g(x)\right)$. –  fgp Mar 9 at 15:02
    
I see why the last is preferred, thanks for noting this. –  AnnieOK Mar 9 at 15:19

Observe that if the limit exists, $$\lim_{n\to\infty}\left|\frac{a_n}{b_n}\right|<\infty\Longleftrightarrow a_n=\mathcal O(b_n)$$

Can you compute $\lim\limits_{n\to\infty}\frac{2^{2n+1}}{2^{2n}}$ and $\lim\limits_{n\to\infty}\frac{2^n}{2^\frac n2}\ $?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.