Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer
    
Thank you so much for your direct and concise answer! –  Ryan Mar 22 '12 at 20:43

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.