# Asymptotic Little-o proof

I'm asked to prove or disprove the following theorem:

$$T_1(N) = O(f(N)) \land T_2(N) = O(f(N)) \Longrightarrow (T_1(N) - T_2(N)) = o(f(N))$$

I have following proof for why the above theorem is false but I don't know if its correct:

Proof:

By the definition of Big-O

$$T_1(N) = O(f(N)) \Rightarrow \exists c_1, N_1 \in \mathbb{R}^+, \forall N \ge N_1, \ T_1(N) \le c_1*f(N)$$

$$T_2(N) = O(f(N)) \Rightarrow \exists c_2, N_2 \in \mathbb{R}^+, \forall N \ge N_2, \ T_2(N) \le c_2*f(N)$$

It follows then that,

$$\forall N \ge max(N_1, N_2), \quad T_1(N) \le c_1*f(N) \quad \land \quad T_2(N) \le c_2*f(N)$$

which in turn means that,

$$\forall N \ge max(N_1, N_2), \quad T_1(N) - T_2(N) \le (c_1f(N) - c_2 f(N))$$

$$\Rightarrow T_1(N) - T_2(N) \le (c_1 - c_2)f(N) \Rightarrow T_1(N) - T_2(N) = O(f(n))$$

It also means that,

$$\forall N \ge max(N_1,N_2), \quad T_1(N) \ge \frac{1}{c_1}*f(N) \quad \land \quad T_2(N) \ge \frac{1}{c_2}*f(N)$$

$$\Rightarrow T_1(N) - T_2(N) \ge \frac{1}{c_1}*f(N) - \frac{1}{c_2}*f(N)$$

$$\Rightarrow T_1(N) - T_2(N) \ge (\frac{1}{c_1} - \frac{1}{c_2}) * f(N)$$

$$\Rightarrow T_1(N) - T_2(N) = \Omega(f(N))$$

Since $$T_1(N) - T_2(N) = O(f(N))$$ but $$T_1(N) - T_2(N) = \Theta(f(N))$$ it follows that $$T_1(N) - T_2(N) \ne o(f(N))$$

You are subtracting inequalities which is false, in general. Consider $$3\leq 4$$ and $$1\leq 3$$. It's not true that $$3-1\leq 4-3$$. As a result, some of your conclusions are wrong. $$T_1(N)-T_2(N)=\Omega(f(N))$$ doesn't follow from the hypotheses.
To prove the statement is false, it's enough to show a counterexample. For instance, $$2n\in O(n)$$ and $$n\in O(n)$$ but $$2n-n=n\notin o(n)$$ because $$\lim_{n\to\infty}\frac{n}{n}=1\ne 0$$.