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 have some questions to prepare for exam on Big-O as follows:

  1. $2^{2n} = O(2^n)$
  2. $40^n = O(2^n)$
  3. $(2n)! = O(n!)$
  4. $(n+1)^{40} = O(n^{40})$

Please could someone advise if my attempted solutions are on the right track.

  1. $2^{2n}= 2^n\cdot 2^n \le c\cdot 2^n \Rightarrow 2^n \le c$. As there is no constant greater than $2^n$, this statement is false.
  2. Again, this is false as it is the case that a real number $(B)$ and a non-negative real number $b$ don't exist to fulfil \[ |f(x)| \le B|g(x)| \text{ for all real numbers $x>b$} \]
  3. This is false for the same reason given in 2.) above
  4. This is true as the Big-O estimate approximates to the highest power?

Many thanks

share|improve this question
3  
The brief answers (FFFFT) are all correct, so your intuition about the relative size of the items is good. The explanations are in my opinion insufficient. The explanation for $(1)$ comes very close to being fully adequate, just a small matter of wording. –  André Nicolas Oct 8 '12 at 14:32
    
Thanks for the feed back Andre. On point one, if I said there is no c greater than all 2^n or in other words as n grows to be a large number. Would this be sufficient? Cheers man –  bosra Oct 8 '12 at 14:59

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.