Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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|cite|improve this answer

I found the answer to my own question in the new/4th edition of the textbook, available at . Here's the relevant portion:

enter image description here

share|cite|improve this answer

Your Answer


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.