1
$\begingroup$

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?

$\endgroup$
2
  • 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, 2012 at 3:56
  • $\begingroup$ The problem is to prove small-o. $\endgroup$
    – sam
    Oct 21, 2012 at 8:15

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I'm not quite understand how you choose N? Thank you~ $\endgroup$
    – sam
    Oct 27, 2012 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, 2012 at 7:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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