Here is my proof, but I am not sure whether it is correct.

We know:

$\qquad \begin{array}{l} \forall {c_1},\exists {n_1},0 \le f\left( n \right) \le {c_1}g\left( n \right),\forall n \ge {n_1} \\ \forall {c_1},\exists {n_2},0 \le g\left( n \right) \le {c_1}h\left( n \right),\forall n \ge {n_2} \\ \end{array}$

Hope to prove:

$\qquad \begin{array}{l} \forall c,\exists {n_0},0 \le f\left( n \right) \le ch\left( n \right),\forall n \ge {n_0} \\ \Rightarrow 0 \le f\left( n \right) \le {c_1}g\left( n \right) \le {c_1}\left( {{c_1}h\left( n \right)} \right),\forall n \ge \max \left\{ {{n_1},{n_2}} \right\} \\ \end{array}$

Let $c = {c_1}^2$. Then,

$\qquad 0 \le f\left( n \right) \le {c^2}h\left( n \right),\forall n \ge {n_0} = \max \left\{ {{n_1},{n_2}} \right\}$

Is there any mistake?

  • 1
    $\begingroup$ seems more-or-less OK (the constants need not be the same). However, this is Big-O rather than small-O, right? $\endgroup$
    – Ran G.
    Oct 21 '12 at 3:56
  • $\begingroup$ The problem is to prove small-o. $\endgroup$
    – sam
    Oct 21 '12 at 8:15

Comment on your proof: You write "Let $c = {c_1}^2$." Strictly speaking, this doesn't make sense, since you haven't set $c_1$ to any value yet at this point. To be formally correct, you need to start with some given $c$, and then set $c_1$ to $\sqrt{c}$ and proceed from there (which is what I've done below where $\epsilon = c$).

To show that $f(n) \in o(h(n))$, you need to show that $\lim_{n\rightarrow\infty}\frac{f(n)}{h(n)}=0$. Or, in other words, for any constant $\epsilon$, there exists $N>0$ such that $$ \forall n \geq N\colon |f(n)| \leq \epsilon|h(n)|. \qquad \text{(A)} $$ Before proving (A), let's write out our assumptions explicitly: Since we have assumed $f(n) \in o(g(n))$, we know that for any $\epsilon$, there exists an $N_f$ such that $$\forall n \geq N_f\colon |f(n)| \leq \epsilon |g(n)|. \qquad\text{(1)}$$ Analogously, by $g(n) \in o(h(n))$, we know that there is $N_g$ such that $$ \forall n \geq N_g\colon |g(n)| \leq \epsilon |h(n)|, \quad\text{(2)} $$ for any given $\epsilon$.

Proof of (A): Suppose we are given some $\epsilon$. Let $$N = \max\left(N_f(\sqrt{\epsilon}),N_g(\sqrt{\epsilon})\right),$$ where $N_f(\sqrt{\epsilon})$ and $N_g(\sqrt{\epsilon})$ are constants that make (1) and (2) true for $\sqrt{\epsilon}$. It follows that $$ \sqrt{\epsilon} > \frac{|g(n)|}{|h(n)|} > \frac{(1/\sqrt{\epsilon})|f(n)|}{|h(n)|}, $$ and therefore $|f(n)| \leq \epsilon |h(n)|$, as required.

  • $\begingroup$ I'm not quite understand how you choose N? Thank you~ $\endgroup$
    – sam
    Oct 27 '12 at 11:39
  • $\begingroup$ We want to choose $N$ large enough, such that for all $n\ge N$, it holds that $\frac{|f(n)|}{|g(n)|}\le\sqrt{\epsilon}$ and $\frac{|g(n)|}{|h(n)|}\le\sqrt{\epsilon}$. Thus we set $N$ to the maximum of $N_f(\sqrt{\epsilon})$ and $N_g(\sqrt{\epsilon})$. $\endgroup$
    – Peter
    Oct 28 '12 at 7:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.