But the book asks me to prove that it's correct: $$n^{2^n} + 6*2^n = O(2^{2^n})$$ But I think, it's an incorrect one. Because, it's correct only for $n < 2$.
Asked
Active
Viewed 57 times
0
-
you prob want to edit the title. and prob a typo, shouldn'tt it be 2 in the first term? – Lost1 Dec 07 '13 at 13:31
-
Oh! You meant "big O"... – Julien Dec 07 '13 at 14:28
-
@Lost1 I carefully checked the first term, because it seems wrong to me. – Bek Abdik Dec 08 '13 at 05:10
1 Answers
1
$$f(x)=O(g(x))\quad\mbox{ iff }\quad\limsup_{x\rightarrow\infty}\frac{f(x)}{g(x)}<\infty$$
But
$$\limsup_{n\rightarrow\infty}\frac{n^{2^n}}{2^{2^n}}=\limsup_{n\rightarrow\infty}\left(\frac{n}{2}\right)^{2^n}=\infty$$
Hence $n^{2^n}\neq O(2^{2^n})$
Xoff
- 10,310