O-Notation: How to put the function in order.

Question

I am new here, so I am sorry for any mistake that I'll probably make. I have an exercise to solve, but I didn't really understand how this really works.

I am given the functions $2^n$, $n^{0.01}$, $\log n$, $\log(n^3)$, $n \log n$, $n^n$, $1$, $\log \log n$, $\sqrt{n}$, $\frac{1}{n}$, $n!$, $\log(n^{\log n})$, $8^n$ and $n^8$. And the question that they made to me is:

Sort the above functions in asymptotically ascending direction.

I don't want the solution, but a good explanation so that I can understand how to solve it.

Is there any video of explaining in plain English how I can sort the functions?

Answer 1

Congratulations! You have just won the lottery! You will receive cash every week for the rest of your life, on one of two schedules:

1. \$1,000 today, \$1,002 next week, \$1,004 the week after that, and so on, \$1006, \$1008, \$1010… OR
2. \$0.05 today, \$0.10 next week, \$0.20 the week after that, and so on, \$0.40, \$0.80, \$1.60…

The first one gets you more money right away, but if you can wait a few months for your money, schedule 2 is much better, because after a few months the schedule 2 payments reach \$1638.40, and after that they are always larger than the schedule 1 payments.

In this case, we say that the second schedule is asymptotically greater than the first schedule. This means that if you wait long enough, the payments of the second schedule will always be greater than the payments of the first schedule.

The formula for the payments is that in the $n$th week, the first schedule pays $2n+998$ dollars, while the second schedule pays $\frac{2^n}{40}$ dollars. The function $\frac{2^n}{40}$ is asymptotically greater than the function $2n+998$, because $\frac{2^n}{40}$ is always greater than $2n+998$, not right away, but when $n$ is large enough.

Your job is to look at those 11 functions and put them in order according to which ones are asmyptotically greatest. For example, do you prefer a lottery prize that pays \$1 every week, or a prize that pays \$$n!$ every week? Obviously the second one, because after a couple of weeks its prizes are always greater than \$1. So the function $n!$ is asymptotically greater than the function $1$. Do you prefer a lottery prize of $8^n$ dollars in week $n$, or $n!$ dollars in week $n$? Well, the $8^n$ prize is 8 times bigger every week than the previous week, but after week $8$, the $n!$ prize is more than 8 times bigger than the previous week, so if you wait long enough it must catch up to the $8^n$ prize and exceed it.

Answer 2

We say that $f\in O\left(g\right)$ (as $n\rightarrow \infty$) if there exists $C>0$ and $N$ sufficiently large s.t. $\left|f\left(n\right)\right|\leq C\left|g\left(n\right)\right|$ for all $n\geq N$. For example, $\log n\leq\log n^{3}$ for all $n\geq1$, and hence $\log n\in O\left(\log n^{3}\right)$. The assignment asks you to order all of these functions $f_{1}$, $f_{2}$, ..., $f_{n}$ so that $$ f_{k}\in O\left(f_{k+1}\right). $$ For example, $$ n,n^{2},n^{3},n^{4},... $$ would be an ordering of the functions $\left\{ f_{k}=n^{k}\right\} $.

Answer 3

Some basic facts that will help you: $(\log n)^c = O(n^d)$ for any $c,d > 0$. You can prove this with basic calculus. Also $n^d = O(c^n)$ for any $d > 0$ and $c > 1$ (also can be shown with calculus).