3
$\begingroup$

Using the basic definition of theta notation prove that $\max(f(n), g(n)) = \Theta(f(n) + g(n))$

I came across two answer to this question on this website but the answers weren't clear to me. Would you mind to elaborate how this can be proven? I am first year student of computer sciences. Thank you!

Edit:

What exactly does $\max(f(n), g(n))$ return?

  • 0
    You can refer to this question: [http://stackoverflow.com/questions/12791306/prove-fn-gn-is-omaxfn-gn]2017-02-11

2 Answers 2

8

Note that $f(n) \leq f(n) + g(n)$ and $g(n) \leq f(n) + g(n)$. Hence, $\max(f(n), g(n)) \in \mathcal{O}(f(n) + g(n))$ Next note that $f(n) + g(n) \leq 2 \max(f(n),g(n))$. Hence, $\max(f(n), g(n)) \in \mathcal{\Omega}(f(n) + g(n))$ Hence, we get that $\max(f(n), g(n)) \in \mathcal{\Theta}(f(n) + g(n))$

Note that $\max(f(n),g(n)) = \begin{cases} f(n) & \text{if } f(n) \geq g(n)\\ g(n) & \text{if } g(n) \geq f(n) \end{cases}$ For instance, if $f(n) = 10n$ and $g(n) = n^2$, we get that $\max(f(n),g(n)) = \begin{cases} 10n & \text{if } n \leq 10\\ n^2 & \text{if } n \geq 10 \end{cases}$

  • 0
    @MaryStar what u concluded about your above question? I feel yes because by reflexive nature of $\Theta$, $f(n)+g(n)=\Theta(f(n)+g(n))$ and $max\{f(n),g(n)\}=\Theta(max\{f(n),g(n)\})$. Please confirm. (just having doubt whether we can put $\Theta(max\{f(n),g(n)\})=max\{f(n),g(n)\}$)2016-05-02
0

I think this can be done to prove this:

to prove: $\max(f(n),g(n))=\Theta(f(n)+g(n))$

$c_1(f(n)+g(n)) \leq\max(f(n),g(n))\leq c_2(f(n)+g(n))$

$\max(f(n),g(n)) \leq 1(f(n)+g(n))$

$\max(f(n),g(n)) \geq \frac12(f(n)+g(n))$

$\implies$ so it holds true for $c_1\leq\frac12$ and $c_2\geq1$

  • 0
    Welcome to MSE. Please use [MathJax](https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference).2017-08-19