0
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\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, 2018 at 6:15

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$

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