Page 236 - Discrete Mathematics and Its Applications

3.2 The Growth of Functions 215

Often, it is important to know the order of growth of a function in terms of some relatively
n
x
simple reference function such as x when n is a positive integer or c , where c> 1. Knowing
the order of growth requires that we have both an upper bound and a lower bound for the size of
the function. That is, given a function f(x), we want a reference function g(x) such that f(x)
is O(g(x)) and f(x) is (g(x)). Big-Theta notation, defined as follows, is used to express both
of these relationships, providing both an upper and a lower bound on the size of a function.

DEFINITION 3 Let f and g be functions from the set of integers or the set of real numbers to the set of real
numbers. We say that f(x) is (g(x)) if f(x) is O(g(x)) and f(x) is (g(x)). When f(x)
is (g(x)) we say that f is big-Theta of g(x), that f(x) is of order g(x), and that f(x) and
g(x) are of the same order.

When f(x) is (g(x)), it is also the case that g(x) is (f (x)). Also note that f(x) is (g(x))
if and only if f(x) is O(g(x)) and g(x) is O(f (x)) (see Exercise 31). Furthermore, note that
f(x) is (g(x)) if and only if there are real numbers C 1 and C 2 and a positive real number k
such that

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

whenever x> k. The existence of the constants C 1 , C 2 , and k tells us that f(x) is (g(x)) and
that f(x) is O(g(x)), respectively.
Usually, when big-Theta notation is used, the function g(x) in (g(x)) is a relatively simple
x
n
reference function, such as x , c , log x, and so on, while f(x) can be relatively complicated.
2
EXAMPLE 11 We showed (in Example 5) that the sum of the first n positive integers is O(n ). Is this sum of
2
order n ?
2
Solution: Let f (n) = 1 + 2 + 3 + ··· + n. Because we already know that f (n) is O(n ),to
2
2
show that f (n) is of order n we need to find a positive constant C such that f (n)>Cn for
sufficiently large integers n. To obtain a lower bound for this sum, we can ignore the first half
of the terms. Summing only the terms greater than n/2 , we find that
1 + 2 + ··· + n ≥ n/2 + ( n/2 + 1) + ··· + n

≥ n/2 + n/2 +· · ·+Ðn/2
= (n −Ðn/2 + 1) n/2
≥ (n/2)(n/2)
2
= n /4.
2
2
This shows that f (n) is (n ). We conclude that f (n) is of order n , or in symbols, f (n) is
2
(n ). ▲

2
2
EXAMPLE 12 Show that 3x + 8x log x is (x ).
2
2
Solution: Because 0 ≤ 8x log x ≤ 8x , it follows that 3x + 8x log x ≤ 11x 2 for x> 1.
2
2
2
Consequently, 3x + 8x log x is O(x ). Clearly, x 2 is O(3x + 8x log x). Consequently,
2
2
3x + 8x log x is (x ). ▲