# Introduction to Algorithms

Chapter03 - Home
Exercises: 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12 - 13 - 14 - 15 - 16 - 17 - 18 - 19 - 20 - 21

Exercise. This is the solution to exercise 3.1-1 in the book.

Solution. We have that

$\Theta \left(f\left(n\right)+g\left(n\right)\right)=\left\{h\left(n\right)\right\}$

with

$0\le {c}_{1}\left[f\left(n\right)+g\left(n\right)\right]\le h\left(n\right)\le {c}_{2}\left[f\left(n\right)+g\left(n\right)\right]$

Is $max\left(f\left(n\right),g\left(n\right)\right)$ in the set of these functions? Since both $f\left(n\right)$ and $g\left(n\right)$ are asymptotically non-negative, then $\exists n\ge {n}_{0}$ such that $f\left(n\right)\ge 0$ and $g\left(n\right)\ge 0$. Therefore, we have that (for $n\ge {n}_{0}$):

$f\left(n\right)+g\left(n\right)\ge f\left(n\right)\ge 0\phantom{\rule{1em}{0ex}}f\left(n\right)+g\left(n\right)\ge g\left(n\right)\ge 0$

Since $max\left(f\left(n\right),g\left(n\right)\right)$ equals either $f\left(n\right)$ or $g\left(n\right)$ then

$0\le max\left(f\left(n\right),g\left(n\right)\right)\le f\left(n\right)+g\left(n\right)$

We have that:

$\frac{1}{2}f\left(n\right)\le \frac{1}{2}max\left(f\left(n\right),g\left(n\right)\right)$

$\frac{1}{2}g\left(n\right)\le \frac{1}{2}max\left(f\left(n\right),g\left(n\right)\right)$

Hence,

$0\le \frac{1}{2}\left[f\left(n\right)+g\left(n\right)\right]\le max\left(f\left(n\right),g\left(n\right)\right)$

Therefore

$0\le \frac{1}{2}\left[f\left(n\right)+g\left(n\right)\right]\le max\left(f\left(n\right),g\left(n\right)\right)\le f\left(n\right)+g\left(n\right)$

Hence,

$max\left(f\left(n\right),g\left(n\right)\right)=\Theta \left(f\left(n\right)+g\left(n\right)\right)$

with ${c}_{1}=\frac{1}{2}$ and ${c}_{2}=1$ and some ${n}_{0}$.