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
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


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

Browse other questions tagged or ask your own question.