0

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.

Danny_Kim
  • 3,423
  • I would find it easiest to prove it in two steps: (a) $O(f)\subseteq O(g)$ exactly when $f\in O(g)$ because asymptotic bounding is a transitive relation; (b) if $\lim f/g=0$ then $f\in O(g)$. – hmakholm left over Monica Oct 12 '15 at 13:11
  • More to the point of your question: Your proof needs a lot more words rather than just symbols. There's no particular virtue in trying to cram everything into symbolic shorthand instead of actual words and sentences. We have the symbolic representation because sometimes we need it to express things that would be too convoluted to say in words, but whenever something can be said in words, words are better! – hmakholm left over Monica Oct 12 '15 at 13:14
  • Also, never write things such as $\exists n_0 ; s.t. ; \text{(something)}, \forall n$. (a) Having one quantifier before the (something) and one after makes it unclear which one is in the range of the other. (b) Quantifiers should never be placed after the formula they range over anyway. (c) Don't use "s.t." with symbolic quantifiers -- the notation "$\exists x,\phi(x)$ is pronounced "there exists an $x$ such that $\phi(x)$"; the $\exists$ symbol expresses this entire meaning. – hmakholm left over Monica Oct 12 '15 at 13:18
  • so far, I knew that using symbols are better than not using them. Thank you for good advice. – Danny_Kim Oct 12 '15 at 13:35
  • @HenningMakholm Can I ask how to prove that $f\in O(g)$ is equal to $O(f) \subseteq O(g)$? I already tried to do that, but failed. As I wrote above, I cannot prove when $0<k<1$ case. – Danny_Kim Oct 12 '15 at 13:43
  • The core fact you need to prove is that if $h\in O(f)$ and $f\in O(g)$ then $h\in O(g)$, from the definitions. This gives you $f\in O(g)\implies O(f)\subseteq O(g)$. The other direction is immediate because clearly $f\in O(f)$. – hmakholm left over Monica Oct 12 '15 at 13:47

0 Answers0