Page 234 - Discrete Mathematics and Its Applications

3.2 The Growth of Functions 213

when x> k 2 . To estimate the sum of f 1 (x) and f 2 (x), note that

|(f 1 + f 2 )(x)|=|f 1 (x) + f 2 (x)|
≤|f 1 (x)|+|f 2 (x)| using the triangle inequality |a + b|≤|a|+|b|.

When x is greater than both k 1 and k 2 , it follows from the inequalities for |f 1 (x)| and |f 2 (x)|
that

|f 1 (x)|+|f 2 (x)|≤ C 1 |g 1 (x)|+ C 2 |g 2 (x)|
≤ C 1 |g(x)|+ C 2 |g(x)|
= (C 1 + C 2 )|g(x)|
= C|g(x)|,

where C = C 1 + C 2 and g(x) = max(|g 1 (x)|, |g 2 (x)|). [Here max(a, b) denotes the maximum,
or larger, of a and b.]
This inequality shows that |(f 1 + f 2 )(x)|≤ C|g(x)| whenever x> k, where k =
max(k 1 ,k 2 ). We state this useful result as Theorem 2.

THEOREM 2 Suppose that f 1 (x) is O(g 1 (x)) and that f 2 (x) is O(g 2 (x)). Then (f 1 + f 2 )(x) is
O(max(|g 1 (x)|, |g 2 (x)|)).

We often have big-O estimates for f 1 and f 2 in terms of the same function g. In this situation,
Theorem 2 can be used to show that (f 1 + f 2 )(x) is also O(g(x)), because max(g(x), g(x)) =
g(x). This result is stated in Corollary 1.

COROLLARY 1 Suppose that f 1 (x) and f 2 (x) are both O(g(x)). Then (f 1 + f 2 )(x) is O(g(x)).

In a similar way big-O estimates can be derived for the product of the functions f 1 and f 2 .
When x is greater than max(k 1 ,k 2 ) it follows that

|(f 1 f 2 )(x)|=|f 1 (x)||f 2 (x)|

≤ C 1 |g 1 (x)|C 2 |g 2 (x)|
≤ C 1 C 2 |(g 1 g 2 )(x)|
≤ C|(g 1 g 2 )(x)|,

where C = C 1 C 2 . From this inequality, it follows that f 1 (x)f 2 (x) is O(g 1 g 2 (x)), because
there are constants C and k, namely, C = C 1 C 2 and k = max(k 1 ,k 2 ), such that |(f 1 f 2 )(x)|≤
C|g 1 (x)g 2 (x)| whenever x> k. This result is stated in Theorem 3.

THEOREM 3 Suppose that f 1 (x) is O(g 1 (x)) and f 2 (x) is O(g 2 (x)). Then (f 1 f 2 )(x) is O(g 1 (x)g 2 (x)).

The goal in using big-O notation to estimate functions is to choose a function g(x) as simple
as possible, that grows relatively slowly so that f(x) is O(g(x)). Examples 8 and 9 illustrate
how to use Theorems 2 and 3 to do this. The type of analysis given in these examples is often
used in the analysis of the time used to solve problems using computer programs.