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?

  • 2
    It's not true in general without some condition, the most obvious being that both are positive functions.2012-12-29
  • 0
    @ThomasAndrews is "both are positive functions" the only condition? Am not able to guess any other condition for which above hold2016-05-02
  • 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
    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?2012-12-29
  • 0
    @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))$$2012-12-29
  • 0
    That makes more sense. However, how did you get to f(n) + f(n) or g(n) + g(n) ?2012-12-29
  • 0
    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.2012-12-29
  • 0
    Ok I'm off to try and figure this out to the core. Thanks for your help and time. Answer accepted2012-12-29
  • 0
    in the solutions to intro to algo.. exercises i found the following answer the my q. Part 1: "First, lets clarify what the function max( f (n), g(n)) is. Lets deÞne the function h(n) = max( f (n), g(n)). Then h(n) = f (n) if f (n) ≥ g(n) , g(n) if f (n) < g(n) ."2012-12-29
  • 0
    Part 2: Since f (n) and g(n) are asymptotically nonnegative, there exists n0 such that f (n) ≥ 0 and g(n) ≥ 0 for all n ≥ n0. Thus for n ≥ n0, f (n) + g(n) ≥ f (n) ≥ 0 and f (n)+g(n) ≥ g(n) ≥ 0. Since for any particular n, h(n) is either f (n) or g(n), we have f (n) + g(n) ≥ h(n) ≥ 0, which shows that h(n) = max( f (n), g(n)) ≤ c2( f (n) + g(n)) for all n ≥ n0 (with c2 = 1 in the deÞnition of ).2012-12-29
  • 0
    Part 3: Similarly, since for any particular n, h(n) is the larger of f (n) and g(n), we have for all n ≥ n0, 0 ≤ f (n) ≤ h(n) and 0 ≤ g(n) ≤ h(n). Adding these two inequalities yields 0 ≤ f (n) + g(n) ≤ 2h(n), or equivalently 0 ≤ ( f (n) + g(n))/2 ≤ h(n), which shows that h(n) = max( f (n), g(n)) ≥ c1( f (n)+g(n)) for all n ≥ n0 (with c1 = 1/2 in the deÞnition of ).2012-12-29
  • 0
    I am probably wrong for saying this but somehow your explanation and this one don't look the same?2012-12-29
  • 0
    @Peter I do not understand why you you think mine is different from your textbook's solution. Both are in fact the same solution.2012-12-29
  • 0
    Never mind. Thanks for your help. So basically you get the upper bound, and the lower bound. Based on that we get Theta, correct?2012-12-29
  • 0
    @Peter No. I did not find you rude at all. Yes, if you look at my first comment, I have shown you how to obtain the inequality by making use of the fact that $f(n) \leq \max(f(n),g(n))$ and $g(n) \leq \max(f(n),g(n))$ and adding them both.2012-12-29
  • 0
    @Peter Yes. essentially you have that $$\dfrac{f(n) + g(n)}2 \leq \max(f(n),g(n)) \leq f(n) + g(n)$$ and hence you conclude that $\max(f(n),g(n)) \in \Theta(f(n) + g(n))$.2012-12-29
  • 0
    Does the reverse also stand?? So, is: $$f(n)+g(n)=\Theta (\max \{f(n),g(n) \})$$ true??2014-10-01
  • 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))=0(f(n)+g(n)) //consider 0 as big theta notation

c1(f(n)+g(n)) <= max(f(n),g(n)) <= c2(f(n)+g(n))

max(f(n),g(n)) <= 1(f(n)+g(n))

max(f(n),g(n)) >= (1/2)(f(n)+g(n))

=>so it holds true for c1<=1/2 and c2>=1

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