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

  • $\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

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)$.


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