$\lim_{n\to\infty}\frac{f(n)}{h(n)}$ if $f\in o(g)$ and $g\in O(h)$

Question

I would appreciate it if anybody could check my attempted solution to this question. I'm guessing since the question says 'values' rather than 'value' that I haven't finished the question. So if you could let me know if I've finished or point me in the direction of finding the other solutions, it would be much appreciated.

Question: Let f, g and h be three functions from $ \mathbb N$ to $\mathbb N$. Assume that f $\in$ o(g) and g $\in$ O(h). If the limit of f(n)/h(n) exists as n $\to \infty$ what are its possible values?

My attempt:

Since f $\in$ o(g), $\exists c_1 > 0$ such that f(n) $<c_1g(n)$ $\forall n \in \mathbb N$ and since $g \in O(h), \exists c_2 > 0$ such that $g(n) \leq h(n) \forall n\in \mathbb N $.

So $f \in o(h)$ also. Therefore $\lim_{n\to\infty}\frac{f(n)}{h(n)} = 0$

Answer 1

You have the definitions somewhat wrong.

• $f\in o(g)$ means that for every $\epsilon>0$ there exists an $N_1\in \Bbb N$ such that $f(n)<\epsilon g(n)$ for all $n>N_1$.
• $g\in O(h)$ means that there exists $c>0$ and $N_2\in\Bbb N$ such that $g(n)\le ch(n)$ for all $n>N_2$.

Nevertheless, let $L=\lim_{n\to\infty}\frac{f(n)}{h(n)}$. If $L>0$, then with $c,N_2$ as above we let $\epsilon=\frac L{2c}$ and find $N_1$ accordingly. Then for $n>\max\{N_1,N_2\}$ we have $$f(n)<\epsilon g(n)=\frac L{2c}g(n) \le \frac L2 h(n)$$ and hence $\frac{f(n)}{h(n)}<\frac L2$, leading to a contradiction. We conclude that $L=0$.