The Algorithm Design Manual Second Edition

2.4

Working with the Big Oh

You learned how to do simplifications of algebraic expressions back in high school.

Working with the Big Oh requires dusting off these tools. Most of what you learned

there still holds in working with the Big Oh, but not everything.

2.4.1

Adding Functions

The sum of two functions is governed by the dominant one, namely:

O(f (n)) + O(g(n))

→ O(max(f(n), g(n)))

Ω(f (n)) + Ω(g(n))

→ Ω(max(f(n), g(n)))

Θ(f (n)) + Θ(g(n))

→ Θ(max(f(n), g(n)))

This is very useful in simplifying expressions, since it implies that n

3

+ n

2

+

n + 1 = O(n

3

). Everything is small potatoes besides the dominant term.

The intuition is as follows. At least half the bulk of f (n) + g(n) must come

from the larger value. The dominant function will, by definition, provide the larger

value as n

→ ∞. Thus, dropping the smaller function from consideration reduces

the value by at most a factor of 1/2, which is just a multiplicative constant. Suppose

f (n) = O(n

2

) and g(n) = O(n

2

). This implies that f (n) + g(n) = O(n

2

) as well.