Let f(n) and g(n) be asymptotically non-negative functions. Using the basic definition of

Question

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?

Answer 1

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))$.

Answer 2

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