How do I approach arranging functions so that each function is big O of the next function?

Question

The specific question I have to work on is:

$\sqrt{n}$ , $\log{n^{100}, }$ $\ n^{10}$, $\log(10^n)$ , $\log(n^n)$, $\ n!$, $\ 3^n$, $\log(n!)$

The way I approached this was just choosing a large value for $\ n= 100$, and just putting them by order of least to greatest output. However, as this results in some really big outputs, I'm not sure if my result is accurate.

My answer: $\sqrt{n}$ , $\log{n^{100}, }$ $\log(10^n)$ , $\log(n!)$, $\log(n^n)$, $\ n^{10}$, $\ 3^n$, $\ n!$

I'm fairly confused by the textbook in regards to the growth of functions/big O notation, I understand the basic concept/definition but not how they go about determining this aside from the limit method.

Answer 1

Some hints:

1. $\log\left(a^b\right) = b \log a$, can you apply that to simplify $\log \left(n^{100}\right)$ and $\log \left(10^n\right)$ and $\log\left(n^n\right)$?
2. How do $\sqrt{n}$ and $\log n$ compare in order? (Think L'Hospital's Rule for example)
3. Generally, if $f(n),g(n)$ are functions, you can get a lost of insight in comparing their orders from $$\lim_{n \to \infty} \frac{f(n)}{g(n)}$$

Answer 2

You have the 1st two in the wrong order. Since $(\log x)/x\to 0$ as $x\to \infty,$ we have $\lim_{x\to \infty}(\log (x^A))/x^B=0 $ for any positive $A,B.$

Because $(\log (x^A))/x^B=$ $(A/B)\cdot (\log (x^B))/x^B=$ $(A/B)\cdot (\log x')/x'$ where $x'=x^{A/B}\to \infty$ as $x\to \infty.$

Apply this with $A=1/2, B=100.$

The $=$ sign in "$f(x)=O(g(x))$ as $x\to \infty$" is not literal. It means there exists $K>0$ and $r\in \Bbb R$ such that $|f(x)|\le K|g(x)|$ for all $x>r.$ It does not require that $|f(x)/g(x)|$ converge as $x\to \infty.$

But if $\lim_{x\to \infty}|f(x)/g(x)|$ does exist then $f(x)=O(g(x))$ as $x\to \infty.$

There is also little-$o,$ which also has a non-literal $=$ sign. "$f(x)=o(g(x))$ as $x\to \infty$" means that for $any$ $K>0$ there exists $r_K\in \Bbb R$ such that $|f(x)|\le K|g(x)|$ for all $x>r_K.$

If $f(x)=o(g(x))$ then $f(x)=O(g(x)).$

If $g(x)\ne 0$ for all sufficiently large $x$ then (i): $f(x)=o(g(x))$ iff $\lim_{x\to \infty} f(x)/g(x)=0,$ and (ii): $f(x)=O(g(x))$ iff $\lim_{r\to \infty}\sup_{x>r}|f(x)/g(x))<\infty.$