7

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?

Peter
  • 267

2 Answers2

11

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

  • 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))$$ –  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. –  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
  • 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) ."

     – Peter Dec 29 '12 at 20:21
  • 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 ). – Peter Dec 29 '12 at 20:22
  • 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 ). – Peter Dec 29 '12 at 20:22
  • I am probably wrong for saying this but somehow your explanation and this one don't look the same? – Peter Dec 29 '12 at 20:24
  • @Peter I do not understand why you you think mine is different from your textbook's solution. Both are in fact the same solution. –  Dec 29 '12 at 20:29
  • Never mind. Thanks for your help. So basically you get the upper bound, and the lower bound. Based on that we get Theta, correct? – Peter Dec 29 '12 at 20:36
  • @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. –  Dec 29 '12 at 20:37
  • @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))$. –  Dec 29 '12 at 20:38
  • Does the reverse also stand??

    So, is:

    $$f(n)+g(n)=\Theta (\max {f(n),g(n) })$$

    true??

     – Mary Star Oct 01 '14 at 18:40
  • @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)}$) – Mahesha999 May 02 '16 at 20:15
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$

José Carlos Santos
  • 427,504
Deeksha Pal
  • 1