Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 0 down vote accepted

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$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.