8
$\begingroup$

I understand that when adding functions, the behavior is dominated by the highest power. But what I am having trouble is understanding the proof. Could anyone help me step by step in explaining the proof behind $T_1(n) + T_2(n) = O(max (f(n), g(n)))$ ? Thank you very much.

$\endgroup$
  • $\begingroup$ Do you mean $f(n)+g(n) = O(\max(f(n), g(n)))$? $\endgroup$ – MJD Mar 8 '13 at 1:58
  • $\begingroup$ I guess but doesn't it not matter? If T(n) is in O(f(n)) it doesnt necessarily have to mean that O(f(n)) is the same function does it? $\endgroup$ – user65674 Mar 8 '13 at 3:04
  • $\begingroup$ Well, you didn't state any relation between $T_1$ and $T_2$ on the one hand, and $f$ and $g$ on the other hand, and without that there's no way to say anything about them. Did you mean to say that $T_1(n) = O(f(n))$ and that $T_2(n) = O(g(n))$? $\endgroup$ – MJD Mar 8 '13 at 3:15
  • $\begingroup$ Yes sorry I guess I shouldve specified. I was assuming formal definition of Big O for both T(n) and T2(n) $\endgroup$ – user65674 Mar 8 '13 at 18:50
15
$\begingroup$

Given $T_1(n)=O(f(n))$ and $T_2(n)=O(g(n))$, we are to prove $$T_1(n)+T_2(n)=O(\max(f(n),g(n))\tag0$$

  • Write down exactly what the first assumption says: there exists a constant $C_1$ and an index $N_1$ such that $$|T_1(n)| \le C_1f(n)\quad \text{when } n\ge N_1 \tag1$$

  • Write down exactly what the second assumption says: there exists a constant $C_2$ and an index $N_2$ such that $$|T_2(n)| \le C_2g(n)\quad \text{when } n\ge N_2 \tag2$$

  • Prepare to combine (1) and (2) by introducing $N=\max(N_1,N_2)$ and $C=\max(C_1,C_2)$.

  • Add (1) and (2): $$ |T_1(n)|+|T_2(n)|\le C_1f(n)+C_2g(n) \le C(f(n)+g(n))\quad \text{when } n\ge N \tag3 $$

  • Check that for any two real numbers $a,b$ we have $$a+b\le 2\max(a,b)\tag4$$

  • Use (4) in (3) to obtain $$ |T_1(n)|+|T_2(n)|\le 2C\max(f(n),g(n))\quad \text{when } n\ge N \tag5 $$

  • Conclude that (0) holds.

$\endgroup$
  • 1
    $\begingroup$ Canonical job. +1. $\endgroup$ – Rick Decker Jul 24 '13 at 0:26
  • 1
    $\begingroup$ The Wikipedia article on Big-O asserts that $f_1\in\mathcal O(g_1)$ and $f_2\in\mathcal O(g_2)$ imply $f_1+f_2\in\mathcal O(g_1+g_2)$ (without proof). I can easily see why $f_1+f_2\in\mathcal O(\max\{g_1,g_2\})$, but how can one reconcile the result in the Wiki article with the result proved here? $\endgroup$ – user170231 Apr 25 '18 at 21:00

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.