# How to prove transitivity in small-o of asymptotic analysis?

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?

• seems more-or-less OK (the constants need not be the same). However, this is Big-O rather than small-O, right? – Ran G. Oct 21 '12 at 3:56
• The problem is to prove small-o. – 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.
• 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})$. – Peter Oct 28 '12 at 7:19