# Ordering Equations Using Small-oh Notation.

I have a couple questions about this problem:

Order the following functions $h_i$, for $1 \leq i \leq 5$, with respect to relation $f \prec g$ defined by the small-oh notation as follows: $f \prec g \iff f = o(g)$. \begin{align*} h_1(n) &= (7/6)^{n+3} - 4n^8 \\ h_2(n) &= n^{-2/3} + 3 \cdot \frac{\log^2 n}{n^3} \\ h_3(n) &= \frac{4(n+6)^2}{\log^5 n} + \frac{n^7 \log n}{(3/2)^n} \\ h_4(n) &= 3n - 6 \log_5 n \\ h_5(n) &= n^2 - 9 \log^5 n \end{align*}

1. What does the symbol that is in between f and g mean?

2. How do I used small-oh notation to figure out the order?

In my attempt, I just plugged in $n = 4$ into every $h(n)$ and ordered them from smallest to largest. $$h_1(n) < h_2(n) < h_4(n) < h_5(n) < h_3(n)$$ Am I on the right track with this? What is the correct way to use small-oh to solve this problem?

-
The answer to question 1. is in the sheet. Please have a closer look. – Giuseppe Negro Feb 17 '14 at 22:56
In the sheet? What do you mean? – datprog Feb 17 '14 at 23:00
I mean that the definition of $f\prec g$ is written above. – Giuseppe Negro Feb 17 '14 at 23:10

## 1 Answer

The symbol $\prec$ is defined in your question as $f \prec g$ if and only if $f =o(g)$. The small-oh notation $f = o(g)$ (read "$f$ is a little-o of $g$") means that : $\forall \epsilon > 0$, there exists $N \in \mathbb{N}$, $\forall n \leqslant N$, $\vert f(n) \vert \leqslant \epsilon \vert g(n) \vert$.

A common way to prove that $f = o(g)$ is to use this property : if $g(n)$ in nonzero for all $n$ or becomes non zero for $n$ large enough, $f = o(g)$ if and only if $\frac{f(n)}{g(n)} \longrightarrow 0$ when $n \rightarrow +\infty$.

For instance you have $\frac{h_4(n)}{h_5(n)} \longrightarrow 0$ when $n \rightarrow +\infty$ so $h_4 \prec h_5$

-
Ok, that makes sense. Is there an identity or property I can use to find the formula? – datprog Feb 17 '14 at 23:25
I'm not sure to understand your question. Which formula? – CharlesPerry Feb 17 '14 at 23:33
I'm sorry, I typed the wrong word. Not the formula, the order. – datprog Feb 17 '14 at 23:35
You just have to see if the ratio of two functions goes to 0 as $n$ goes to $+ \infty$ – CharlesPerry Feb 17 '14 at 23:38
I see it now, thanks for the help. – datprog Feb 17 '14 at 23:40