0
$\begingroup$

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))$

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .