0
$\begingroup$

This question already has an answer here:

I saw this relationship in my exercise. max{n,k}= Ө(n+k) Could somebody prove it?

$\endgroup$

marked as duplicate by Raphael Oct 10 '18 at 6:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Use the definitions. Be mindful of what $n$, $k$ mean here, and how the definition of $\Theta$ extends to two parameters. (Hint: it doesn't, really.) $\endgroup$ – Raphael Oct 10 '18 at 6:15
2
$\begingroup$

Assuming n and k to be non-negative, $n\leq n+k$ and $k\leq n+k$. Hence,$\max(n, k) \in \mathcal{O}(n+k)$. Next, $n+k≤2\max(n,k)$. Hence, $\max(n,k)\in\mathcal{\Omega}(n+k)$.
Hence, we get that $\max(n,k)\in \mathcal{\Theta}(n+k)$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.