5
$\begingroup$

1. Let f(n) and g(n) be asymptotically non-negative functions. Using the basic definition of Θ-notation, prove that max{f(n), g(n)} = Θ(f(n) + g(n))

I'm not really quite sure what this question is trying to get out of me.. I'm going to take a stab at it though. First of all I have no idea what "max" is supposed to mean so I'm just going to ignore that and proceed on.

So I know that $f = \Theta(g)$ means $f = O(g)$ and $f = \Omega(g)$

So letting $f = n + 100$ and $g = n + 200$

I know that $f = O(n)$, similarly $g = O(n)$.

Both are $O(n)$ which $\implies f = \Theta(g)$

UPDATE: Yea this doesn't make any sense. This question is implying for me to solve something that isn't true. $max\{f(n),g(n)\} = O(f(n) + g(n))$ letting $c>0$ ... It also holds that $max\{f(n),g(n)\} \ne \Omega(f(n) + g(n))$ ever.. So this question makes no sense.. What am I missing?

$\endgroup$
14
  • 2
    $\begingroup$ "max" is short for "maximum"; it just means the larger of the two numbers. $\endgroup$ Oct 3, 2015 at 2:41
  • $\begingroup$ Also, you are being asked to prove this for all asymptotically non-negative functions $f$ and $g$, not just for one particular pair of functions you get to choose. $\endgroup$ Oct 3, 2015 at 2:42
  • $\begingroup$ Any idea how I go about that? $\endgroup$
    – Shammy
    Oct 3, 2015 at 2:47
  • $\begingroup$ Start by showing each of $f$ and $g$ is $O(f+g)$. Deduce that the max is $O(f+g)$. That's a start. $\endgroup$ Oct 3, 2015 at 2:49
  • $\begingroup$ Ok so... $[(n+ 100) + (n + 200)]$ so $f(n) = n + 100$ and $g(n) = n + 200$ proves that $f + g = O(h) \implies f(n) + g(n) = 2n + 300 \implies O(f(n) + g(n)) = O(n)$ ? $\endgroup$
    – Shammy
    Oct 3, 2015 at 2:58

2 Answers 2

8
$\begingroup$

You don't really have the precise definition of $\Theta$ notation. Given two functions $f$, $g$ defined on $\mathbb N$, we say that $f(n)\in\Theta(g(n)$ if there exist constants $c$, $C$ and a positive integer $n_0$ such that $n\geqslant n_0$ implies that $$ cg(n) \leqslant f(n) \leqslant Cg(n).$$

Since $$\max\{f(n),g(n)\} \leqslant f(n)+g(n) \leqslant 2\max\{f(n),g(n) \} $$ for all $n$, we see that $\max\{f(n),g(n)\}\in\Theta(f(n)+g(n))$.

$\endgroup$
2
  • 1
    $\begingroup$ Finally understood this. Straightforward answer $\endgroup$
    – GabrielBB
    May 6, 2021 at 10:20
  • $\begingroup$ @GabrielBB I was extremely confused at this comment on an answer written over five years ago - until I realized you aren't the one who posted the question. Glad that I was able to help. $\endgroup$
    – Math1000
    May 6, 2021 at 14:48
0
$\begingroup$

I think this is the solution.

We know that $f(n) = \Theta(g(n))$ means $f(n) = O(g(n))$ and similarly $f(n) = \Omega(g(n))$

$m\{f,g\} = O(f+g)$ letting $c>0$

$f + g = O(m\{f,g\})$ letting $c \ge 2$

So basically without getting bogged in notation:

$f = O(g)$ where $ c >0$

Similarly: $g = O(f)$ where $c \ge 2$ which $\implies f = \Omega(g)$

Which $\implies f = \Theta(g)$

$\endgroup$
6
  • $\begingroup$ What do you mean by $m\{f,g\}$? Anyway, there is no reason to think $f=O(g)$. What if $f(n)=n$, and $g(n)=n^2$? Then it's certainly not true that $f=O(g)$. $\endgroup$ Oct 3, 2015 at 23:44
  • $\begingroup$ $m = max$. & are you saying in general or referring to this problem? Because in general if $f(n) = n$ and $g(n) = n^2$ then certainly $f(n) = O(g(n))$.... $\endgroup$
    – Shammy
    Oct 4, 2015 at 0:14
  • $\begingroup$ Sorry, I had that the wrong way around. If $f(n)=n^2$ and $g(n)=n$ then it's certainly not true that $f=O(g)$. $\endgroup$ Oct 4, 2015 at 4:36
  • $\begingroup$ If you type up a solution, I would be happy to review it and decide if it's an acceptable answer but us going back and forth via chat is getting nowhere lol. $\endgroup$
    – Shammy
    Oct 4, 2015 at 21:49
  • $\begingroup$ I'd much rather you work through this and post a correct answer yourself. Anyway, what do you think of the answer posted by @Math1000? $\endgroup$ Oct 4, 2015 at 22:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .