0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ The answer to question 1. is in the sheet. Please have a closer look. $\endgroup$ Commented Feb 17, 2014 at 22:56
  • $\begingroup$ In the sheet? What do you mean? $\endgroup$
    – datprog
    Commented Feb 17, 2014 at 23:00
  • $\begingroup$ I mean that the definition of $f\prec g$ is written above. $\endgroup$ Commented Feb 17, 2014 at 23:10

1 Answer 1

0
$\begingroup$

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$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .