0
$\begingroup$

Possible Duplicate:
how can be prove that $\max(f(n),g(n)) = \theta(f(n)+g(n))$

How to prove $max(f(n),g(n)) = Θ(f(n)+g(n))$?

  • 1
    @robjohn: $f = \Theta(g)$ if _both_ $f = O(g)$ and $g = O(f)$.2011-09-08

1 Answers 1

3

Let $h=\max(f,g)$. Then $f+g\le 2h$ and so $f+g=O(h)$. If $f$ and $g$ are positive, then $h \le f+g$ and so $h=O(f+g)$.