1
$\begingroup$

I know that, $\max(m, n) = O(m+n)$.

But my teacher uses, $$m+n=\Theta(\max\{m, n\}).$$

Anyone explain me why the above expression is true.

$\endgroup$

1 Answer 1

4
$\begingroup$

For $n,m \geq 0$ we have:

$$ \max(n, m) \ \leq \ m + n \ \leq \ 2\cdot \max(n,m) \ .$$

Now, $\max(n, m) =\Theta(\max(n, m))$ and $2\max(n, m) = \Theta(\max(n, m))$, so also the middle term is $\Theta(\max(n, m))$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.