1

I tried to prove that "$o(f(n)) \in O(f(n))$".

I knew intuitively that the proposition is true, through the fact that $n^2=O(n^k), \forall k \ge 2$, but $n^2\ne o(n^k), \forall k>2$.

However, I want to prove this mathematically.

My proof:

$o(g(n)) = \{f(n): \forall c\gt0, \exists n_0>0 \ s.t. 0 \le f(n) \lt cg(n), \forall n \ge n_0\}$

$O(g(n)) = \{f(n): \exists c\gt0, \exists n_0>0 \ s.t. 0 \le f(n) \le cg(n), \forall n \ge n_0\}$

$\forall c > 0$ means "should satisfy for all $c$", while $\exists c>0$ means "should satisfy for some $c$"

$\therefore\{\forall c > 0\} \in \{\exists c>0\}$

Also, $\{f(n) \lt cg(n)\}\in\{f(n) \le cg(n)\}$

$$\therefore o(g(n)) \in O(g(n)) \Leftrightarrow o(f(n)) \in O(f(n))$$

I think my proof is ambiguous and defective because it is proved linguistically, not mathematically.

I hope somebody gives me any direction to prove mathematically. Thank you.

Danny_Kim
  • 3,423

1 Answers1

0

To complete the proof you need to show that there is at least one $c \gt 0$, so that you can go from $\forall c\gt0$ to $\exists c\gt0$; otherwise you may have a vacuous truth. Since the real numbers are an ordered field, $c=1$ is such an example. Thus

$$\forall c\gt0, \exists n_0>0 \ s.t. 0 \le f(n) \lt cg(n), \forall n \ge n_0$$ $$\implies c= 1, \exists n_0>0 \ s.t. 0 \le f(n) \lt cg(n), \forall n \ge n_0$$ $$\implies \exists c\gt0, \exists n_0>0 \ s.t. 0 \le f(n) \lt cg(n), \forall n \ge n_0$$

and thus $f(n)\in o(g(n)) \implies f(n)\in O(g(n))$ and so $o(g(n)) \subseteq O(g(n))$

Henry
  • 157,058
  • It could be only vacuously true if there is no positive real numbers ... That's really picky :D – user251257 Oct 12 '15 at 10:32
  • Thank you. I have to read about ordered field first. – Danny_Kim Oct 12 '15 at 10:52
  • @user251257: Yes, it is picky, but the only two points of any interest are: (a) $o(g(n)) \subseteq O(g(n))$ but $O(g(n)) \not \subseteq o(g(n))$; and (b) you need to choose a positive real number – Henry Oct 12 '15 at 11:03
  • @Danny_Kim: you don't need to worry about ordered fields if you assume there are positive real numbers and you can choose one of them. Since everybody believes this, I found your original proof convincing – Henry Oct 12 '15 at 11:05
  • I read ordered field in wiki~. Is it enough to prove the proposition? with just one example? – Danny_Kim Oct 12 '15 at 11:07
  • @Danny_Kim: You know it is true for all $c\gt 0$ and you are trying to show it is true for at least one $c\gt 0$. So yes, all you need to do is find one example, as it will be true for that example. $1$ is a particularly simple example, but $2$ or $\frac12$ would also work here. – Henry Oct 12 '15 at 11:13