414
Relations, Functions, and Matrices
We will usually try to find the simplest representative of a given equivalence
class. Thus for the functions f and g of Example 44, we would say f = Θ(x
2
) and
g = Θ(x
2
). A polynomial is always the order of magnitude of its highest-degree
term; lower-order terms and all coefficients can be ignored. This is not surprising,
since for large values of x, the highest-degree term will dominate the result.
PRaCtiCe 42 Prove (by finding appropriate constants that satisfy the definition of order of magnitude) that f = Θ(x
2
) and g = Θ(x
2
) for the functions f and g of Example 44.
■
To understand more intuitively what these equivalence classes mean, we’ll
draw some graphs. Let h(x) [ S, where h(x) = x
2
. Figure 5.25 shows the graph
of h(x). Now suppose we multiply the h values by the two constants c 1 = 1∙2 and
c 2 = 2. The functions c 1 h(x) and c 2 h(x) are shown as dotted lines in Figure 5.26.
These dotted lines form a kind of envelope around the h(x) values, roughly tracing the shape of h(x). Changing the value of the constants changes the width of
the envelope but not the basic shape. If h 1 (x) is a function with h 1 = Θ(h), then
there is some positive constant n 0 and some envelope around h such that for all
domain values to the right of n 0 , the h 1 values must fall within this envelope, as
shown in Figure 5.27. Therefore the h 1 values can never stray too far from the h
values. The functions h 1 and h are roughly the same size—they are the same order
of magnitude.
x
h(x) = x 2
x
h(x)
c 2 h(x)
c 1 h(x)
x
h(x)
c 2 h(x)
c 1 h(x)
h 1 (x)
n 0
Figure 5.25
Figure 5.26
Figure 5.27
example 45
Let f (x) = x and h(x) = x
2
. Figure 5.28 illustrates that for the constants c 1 = 1∙2
and c 2 = 2, f soon falls below the envelope. Reducing the c 1 constant (lowering
the bottom edge of the envelope) only postpones the problem. Formally, we can
do a proof by contradiction to show that f is not Θ(x
2
). Suppose f = Θ(x
2
). Then
there exist constants n 0 and c 1 with c 1 x
2
≤ f(x) for x ≥ n 0 . But this would imply
that c 1 x
2
≤ x or c 1 x ≤ 1 or x ≤ 1∙c 1 for all x ≥ n 0 . Because c 1 is fixed, we can
always choose x large enough so that x > 1∙c 1 , which is a contradiction. Therefore
f(x) = x is not Θ(x
2
).
Relations, Functions, and Matrices
We will usually try to find the simplest representative of a given equivalence
class. Thus for the functions f and g of Example 44, we would say f = Θ(x
2
) and
g = Θ(x
2
). A polynomial is always the order of magnitude of its highest-degree
term; lower-order terms and all coefficients can be ignored. This is not surprising,
since for large values of x, the highest-degree term will dominate the result.
PRaCtiCe 42 Prove (by finding appropriate constants that satisfy the definition of order of magnitude) that f = Θ(x
2
) and g = Θ(x
2
) for the functions f and g of Example 44.
■
To understand more intuitively what these equivalence classes mean, we’ll
draw some graphs. Let h(x) [ S, where h(x) = x
2
. Figure 5.25 shows the graph
of h(x). Now suppose we multiply the h values by the two constants c 1 = 1∙2 and
c 2 = 2. The functions c 1 h(x) and c 2 h(x) are shown as dotted lines in Figure 5.26.
These dotted lines form a kind of envelope around the h(x) values, roughly tracing the shape of h(x). Changing the value of the constants changes the width of
the envelope but not the basic shape. If h 1 (x) is a function with h 1 = Θ(h), then
there is some positive constant n 0 and some envelope around h such that for all
domain values to the right of n 0 , the h 1 values must fall within this envelope, as
shown in Figure 5.27. Therefore the h 1 values can never stray too far from the h
values. The functions h 1 and h are roughly the same size—they are the same order
of magnitude.
x
h(x) = x 2
x
h(x)
c 2 h(x)
c 1 h(x)
x
h(x)
c 2 h(x)
c 1 h(x)
h 1 (x)
n 0
Figure 5.25
Figure 5.26
Figure 5.27
example 45
Let f (x) = x and h(x) = x
2
. Figure 5.28 illustrates that for the constants c 1 = 1∙2
and c 2 = 2, f soon falls below the envelope. Reducing the c 1 constant (lowering
the bottom edge of the envelope) only postpones the problem. Formally, we can
do a proof by contradiction to show that f is not Θ(x
2
). Suppose f = Θ(x
2
). Then
there exist constants n 0 and c 1 with c 1 x
2
≤ f(x) for x ≥ n 0 . But this would imply
that c 1 x
2
≤ x or c 1 x ≤ 1 or x ≤ 1∙c 1 for all x ≥ n 0 . Because c 1 is fixed, we can
always choose x large enough so that x > 1∙c 1 , which is a contradiction. Therefore
f(x) = x is not Θ(x
2
).