Big O Notation basics

Question

Having some problems with big O notation question... getting confused on how to figure this out.

I'm working on a problem (exam coming up so doing extra ones) where it asks us to arrange the functions in a list so that every function is big-O of the next.

$$2^{100n}, 2^{n^2}, 2^{n}, n\log n, \log \log n, n^{\frac{1}{2}}, n(\log n)^{1/2}, n^{4/3}(\log n)^2$$

Big O is extremely confusing to me so I don't know where to start..

edit: fiddling around with Latex, please bear with me!

To be clear, you should add "as $n \to \infty$" to the question. And do not use notations like ${=}_a$ or $\prec$ unless your instructor already did. — GEdgar, Jun 27 '15 at 00:47
unfortunately, the question didn't mention any of that. thanks for the advice though! — matthew, Jun 27 '15 at 00:54

Bernard · Answer 1 · 2015-06-27T00:56:44.083

2

$f=_a O(g)$ simply means the quotient $\dfrac fg$ is bounded in a neibourhood of $a$ (except perhaps at $a$ itself).

Here, the functions are classified by the fact that $f=_a o(g)$, i.e. $\dfrac fg\to 0$ when $x\to a$, and noting that $f=_a o(g)$ implies $f=_a O(g)$ . Thus by classical results, we have, in increasing order: $$\log\log n \prec n\log n\prec n^{3/2}\prec n^{4/3}\log^2n\prec 2^{100n}\prec 2^{n^2}\prec2^{n!}$$

edited Jun 27 '15 at 00:56

answered Jun 27 '15 at 00:44

Bernard

175,478

Your "200" should be $2$. – Ian Jun 27 '15 at 00:55
Oops! Thanks for pointing the typo. – Bernard Jun 27 '15 at 00:56
1

where does $2^{2^n}$ land? I assume it will be in between the last two terms? – matthew Jun 27 '15 at 01:17
There's no $2^{2^n}$ in your list! But yes, it would be between the last two terms. – Bernard Jun 27 '15 at 03:18
ah my apologies. it's supposed to be there but nevermind =) thanks! – matthew Jun 27 '15 at 03:34

Big O Notation basics

1 Answers1