Question

Prove that max( f(n), g(n) ) = Ө ( f(n) + g(n) )

Answer 1

We know that,

$f(n)\le f(n)+g(n)$

and $g(n)\le f(n)+g(n)$

Now, $max(f(n),g(n))\in O(f(n)+g(n))$

$\Rightarrow f(n)+g(n)\le 2max(f(n),g(n))$

Hence, $max(f(n),g(n))\le2max(f(n),g(n))$

$\Rightarrow max(f(n),g(n)) \in \Omega(f(n)+g(n))$

$\Rightarrow max(f(n),g(n))\in \theta(f(n)+g(n))$

Hence, we can conclude that

$max(f(n),g(n))=\theta(f(n)+g(n))$