Page 227 - Discrete Mathematics and Its Applications

206 3 / Algorithms

THE HISTORY OF BIG-O NOTATION Big-O notation has been used in mathematics for
more than a century. In computer science it is widely used in the analysis of algorithms, as
will be seen in Section 3.3. The German mathematician Paul Bachmann first introduced big-O
notation in 1892 in an important book on number theory. The big-O symbol is sometimes called
a Landau symbol after the German mathematician Edmund Landau, who used this notation
throughout his work. The use of big-O notation in computer science was popularized by Donald
Knuth, who also introduced the big- and big- notations defined later in this section.

WORKING WITHTHE DEFINITION OF BIG-O NOTATION A useful approach for find-
ing a pair of witnesses is to first select a value of k for which the size of |f(x)| can be readily
estimated when x> k and to see whether we can use this estimate to find a value of C for which
|f(x)|≤ C|g(x)| for x> k. This approach is illustrated in Example 1.

2
2
EXAMPLE 1 Show that f(x) = x + 2x + 1is O(x ).
Solution: We observe that we can readily estimate the size of f(x) when x> 1 because x< x 2
2
and 1 <x when x> 1. It follows that

2
2
2
2
0 ≤ x + 2x + 1 ≤ x + 2x + x = 4x 2
whenever x> 1, as shown in Figure 1. Consequently, we can take C = 4 and k = 1 as witnesses
2
2
2
to show that f(x) is O(x ). That is, f(x) = x + 2x + 1 < 4x whenever x> 1. (Note that it
is not necessary to use absolute values here because all functions in these equalities are positive
when x is positive.)
Alternatively, we can estimate the size of f(x) when x> 2. When x> 2, we have 2x ≤ x 2
2
and 1 ≤ x . Consequently, if x> 2, we have
2
2
2
2
2
0 ≤ x + 2x + 1 ≤ x + x + x = 3x .
2
It follows that C = 3 and k = 2 are also witnesses to the relation f(x) is O(x ).
2
4x 2 x +2x +1 x 2

4

3 2
The part of the graph of f(x) = x +2x +1
2
that satisfies f(x) < 4x is shown in blue.
2

2
2
1 x +2x + 1<4x for x >1

1 2
2
2
FIGURE 1 The Function x + 2x + 1is O(x ).