2

One question on my homework is as follows:

Let $f_1, f_2, f_3, f_4$ be functions from the set $N$ of natural numbers to the set $R$ of real numbers. Suppose that $f_1= O(f_2)$ and $f_3=O(f_4)$. Use the definition of Big Oh given in class to prove that $$f_1(n) + f_3(n) = O(\max(f_2(n), f_4(n))).$$

I have tried to go through the proof, first stating the obvious definitions of Big-$O$ for each of the two relationships listed above. In the next steps, I also tried assuming in one instance that $f_3 = O(f_1)$ and in another that $f_1 = O(f_3)$, to show the resulting relationship that $f_3 = O(f_2)$ and $f_1 = O(f_4)$, respectively. In both assumptions, however, I am unable to tie in BOTH $f_2$ and $f_4$, as is asked for in the question (e.g.$\max(f_2(n), f_4(n)))$). I am stuck.

UnworthyToast
  • 259
  • You should be able to show that $f_2 = O(max(f_2(n), f_4(n))$ and that $f_4 = O(max(f_2(n), f_4(n))$, in which case the transitivity of $O$ should suffice, right? – Hao Ye Sep 23 '14 at 22:23

1 Answers1

2

For large n, $f_1 (n) ≤ c f_2 (n)$ and $f_2 (n) ≤ d f_4 (n)$.

You now use that $a + b ≤ 2 max (a, b)$:

For large n $f_1 (n) + f_3 (n)$ ≤ $c f_2 (n) + d f_4 (n)$ ≤ $(c+d) f_2 (n) + (c+d) f_4 (n)$ = $(c+d) (f_2 (n) + f_4 (n))$ ≤ $2 (c+d) max (f_2 (n), f_4 (n))$.

That means by definition $f_1 (n) + f_3 (n) + O (max (f_2 (n), f_4 (n))$.

gnasher729
  • 10,113