1
$\begingroup$

I'm being introduced to the Big-O notation via Susanna Epp's Discrete Mathematics with Appplications 3rd edition. The following defintion is stated on page 519:

Let f and g be real-valued functions defined on the same set of nonnegative real numbers. Then f is of order at most h, written f is O(h), if, and only if, there exist a positive real number A and a nonnegative real number a such that |f| ≤ A|h| for all real numbers x > a.

And the following theorem is given on page 521:

If f is O(h) and g is O(k), then f+g is O(max(|h|, |k|)) for each x in the domain of the functions.

The proof is left as an exercise, and unfortunately I'm unable to derive the theorem. Instead, I'm getting f+g is O(A |h| + B |k|) which is O(|h| + D |k|).

I feel that I'm misunderstanding the topic, but am unable to see how. Can someone help me please?

3 Answers 3

2

You're almost there. If $D$ is a positive constant, $|h| + D |k| \le (1+D) \max(|h|,|k|)$, so anything that is $O(|h|+D|k|)$ is $O(\max(|h|,|k|)$.

  • 0
    Thank you so much for your direct and concise answer!2012-03-22
1

$f=O(h)$ (resp. $g=O(k)$) means that for any $x\geq N$ (resp. $x\geq N'$), $|f(x)|\leq C|h(x)|$ (resp. $|g(x)|\leq C'|k(x)|$)for some constant $C$ (resp. C').

For any x\geq max(N,N') you have |f(x)+g(x)|\leq |f(x)|+|g(x)|\leq C|h(x)|+C'|k(x)|\leq 2max(C,C') max(h(x),k(x)).

0

I found the answer to my own question in the new/4th edition of the textbook, available at http://www.scribd.com/doc/70067568/Discrete-Mathematics-With-Applications-4th-Edition-by-Susanna-Epp . Here's the relevant portion:

enter image description here