Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
It's not true in general without some condition, the most obvious being that both are positive functions. –  Thomas Andrews Dec 29 '12 at 19:46
add comment

1 Answer 1

up vote 4 down vote accepted

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}$$

share|improve this answer
    
I think I'm starting to get the hang of it. So first we get the upper bound. However what I do not understand is the third and fourth line, namely, "Next note that f(n)+g(n)≤2max(f(n),g(n)). Hence, max(f(n),g(n))∈Ω(f(n)+g(n))". Why is f(n) + g(n) < 2max(f(n), g(n)) ? Basically after we get the upper and lower bounds, we can get the running time, correct? –  Peter Dec 29 '12 at 19:44
    
@Peter For a fixed $n$, if $f(n) \geq g(n)$, then we have that $f(n) +f(n) \geq f(n) + g(n) \implies f(n) + g(n) \leq 2 f(n)$ and if $g(n) \geq f(n)$, then we have that $g(n) +g(n) \geq f(n) + g(n) \implies f(n) + g(n) \leq 2 g(n)$. Hence, we get that $$f(n) + g(n) \leq 2 \max(f(n) + g(n))$$ The key observation is that $f(n) \leq \max(f(n),g(n))$ and $g(n) \leq \max(f(n),g(n))$ and hence $$f(n) + g(n) \leq 2 \max(f(n) + g(n))$$ –  user17762 Dec 29 '12 at 19:49
    
That makes more sense. However, how did you get to f(n) + f(n) or g(n) + g(n) ? –  Peter Dec 29 '12 at 19:54
    
For instance, if we have $f(n) \geq g(n)$ adding $f(n)$ to both sides, we get that $2f(n) \geq f(n) + g(n)$ and similarly for the other case as well. –  user17762 Dec 29 '12 at 19:56
    
Ok I'm off to try and figure this out to the core. Thanks for your help and time. Answer accepted –  Peter Dec 29 '12 at 19:59
show 8 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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