Can someone prove that if lim(f(n)/g(n))=0, then O(f(n)) is subset of O(g(n))?

742 Views Asked by At

Ah!!!! I got discouraged!! Actually, I asked so many times about this O-notation. Thus, I really wanted to solve myself, but I failed... Is my idea totally wrong to approach the proposition ?

$$ if \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=0,\ then\ O(f(n)) \subseteq O(g(n)). $$


My trial:

\begin{align} &\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=0 \longrightarrow f(n) \in\ o(g(n))\\ &\lim_{n\rightarrow\infty}\frac{kf(n)}{g(n)}=0 \longrightarrow \forall c\gt0, \exists n_0>0 \ s.t. 0 \le kf(n) \lt cg(n), \forall n \ge n_0\\ \end{align} for $k \ge 1$, \begin{align} &0 \le f(n) \le kf(n) \lt cg(n) \le cg(n)\\ &\therefore f(n) \in O(f(n)) \subseteq O(g(n)) \end{align}


I think my trial is not correct.

Are there any good methods to prove?

I just can prove linguistically well.

g(n) is asymptotically bigger than f(n), so f(n) < g(n) for big n. Therefore O(f(n)) is subset of O(g(n)). But this is not what I want. Help me.