Page 228 - Discrete Mathematics and Its Applications

3.2 The Growth of Functions 207

2
2
Observe that in the relationship “f(x) is O(x ),” x can be replaced by any function with
2
3
2
larger values than x . For example, f(x) is O(x ), f(x) is O(x + x + 7), and so on.
2
2
2
2
It is also true that x is O(x + 2x + 1), because x <x + 2x + 1 whenever x> 1. This
2
2
means that C = 1 and k = 1 are witnesses to the relationship x is O(x + 2x + 1). ▲
2
2
Note that in Example 1 we have two functions, f(x) = x + 2x + 1 and g(x) = x , such
that f(x) is O(g(x)) and g(x) is O(f (x))—the latter fact following from the inequality
2
2
x ≤ x + 2x + 1, which holds for all nonnegative real numbers x. We say that two func-
tions f(x) and g(x) that satisfy both of these big-O relationships are of the same order.We
will return to this notion later in this section.
Remark: The fact that f(x) is O(g(x)) is sometimes written f(x) = O(g(x)). However, the
equals sign in this notation does not represent a genuine equality. Rather, this notation tells
us that an inequality holds relating the values of the functions f and g for sufficiently large
numbers in the domains of these functions. However, it is acceptable to write f(x) ∈ O(g(x))
because O(g(x)) represents the set of functions that are O(g(x)).
When f(x) is O(g(x)), and h(x) is a function that has larger absolute values than g(x) does
for sufficiently large values of x, it follows that f(x) is O(h(x)). In other words, the function
g(x) in the relationship f(x) is O(g(x)) can be replaced by a function with larger absolute
values. To see this, note that if
|f(x)|≤ C|g(x)| if x> k,

and if |h(x)| > |g(x)| for all x> k, then

|f(x)|≤ C|h(x)| if x> k.
Hence, f(x) is O(h(x)).
When big-O notation is used, the function g in the relationship f(x) is O(g(x)) is chosen
to be as small as possible (sometimes from a set of reference functions, such as functions of the
n
form x , where n is a positive integer).

PAUL GUSTAV HEINRICH BACHMANN (1837–1920) Paul Bachmann, the son of a Lutheran pastor, shared
his father’s pious lifestyle and love of music. His mathematical talent was discovered by one of his teachers, even
though he had difficulties with some of his early mathematical studies. After recuperating from tuberculosis
in Switzerland, Bachmann studied mathematics, first at the University of Berlin and later at Göttingen, where
he attended lectures presented by the famous number theorist Dirichlet. He received his doctorate under the
German number theorist Kummer in 1862; his thesis was on group theory. Bachmann was a professor at Breslau
and later at Münster. After he retired from his professorship, he continued his mathematical writing, played the
piano, and served as a music critic for newspapers. Bachmann’s mathematical writings include a five-volume
survey of results and methods in number theory, a two-volume work on elementary number theory, a book on
irrational numbers, and a book on the famous conjecture known as Fermat’s Last Theorem. He introduced big-O notation in his
1892 book Analytische Zahlentheorie.

EDMUND LANDAU (1877–1938) Edmund Landau, the son of a Berlin gynecologist, attended high school
and university in Berlin. He received his doctorate in 1899, under the direction of Frobenius. Landau first taught
at the University of Berlin and then moved to Göttingen, where he was a full professor until the Nazis forced
him to stop teaching. Landau’s main contributions to mathematics were in the field of analytic number theory.
In particular, he established several important results concerning the distribution of primes. He authored a
three-volume exposition on number theory as well as other books on number theory and mathematical analysis.