Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

1 Answer 1

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|improve this answer
    
Ok, that makes sense. Is there an identity or property I can use to find the formula? –  datprog Feb 17 at 23:25
    
I'm not sure to understand your question. Which formula? –  CharlesPerry Feb 17 at 23:33
    
I'm sorry, I typed the wrong word. Not the formula, the order. –  datprog Feb 17 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 at 23:38
    
I see it now, thanks for the help. –  datprog Feb 17 at 23:40

Your Answer

 
discard

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.