s
Section 5.5 Order of Magnitude
415
x
h(x) = x 2
f (x) = x
c 2 h(x)
c 1 h(x)
Figure 5.28
If we imagine functions representing various forms of transportation, then
functions that are the same order of magnitude (belong to the same equivalence
class) represent the same mode of transportation. One class represents travel on
foot, another class represents travel by automobile, a third represents travel by air.
Speeds within a given mode are about the same; ignoring coefficients and loworder terms amounts to ignoring the difference between walking and running or
between a Jeep and a Jaguar or between a Cessna and a Boeing 787. Walking (at
any speed) is distinctly different from driving, which is distinctly different from
flying.
We can imagine a hierarchy of orders of magnitude. For example, the class
Θ(x) is a lower order of magnitude than the class Θ(x)
2
because functions that are
Θ(x) eventually fall below functions that are Θ(x
2
). Also, the class Θ(log x) is a
lower order of magnitude than Θ(x) (see Exercise 15 at the end of this section). In
our transportation analogy, walking is slower than driving is slower than flying.
A sort of arithmetic can be developed using order of magnitude. For example,
if f 1 (x) = x and f 2 (x) = x
2
, then the function ( f 1 + f 2 )(x) = f 1 (x) + f 2 (x) 5
x + x
2
= Θ(x
2
). In general, if f 1 = Θ(g 1 ) and f 2 = Θ(g 2 ), then f 1 + f 2 5
Θ(max (g 1 , g 2 )) (see Exercise 8). When expressed in abbreviated form,
this leads to somewhat bizarre equations such as Θ(x) + Θ(x
2
) = Θ(x
2
) or
Θ(x
2
) + Θ(x
2
) = Θ(x
2
).
More on analysis of algorithms
Order of magnitude is important in analysis of algorithms, which we discussed in
Section 3.3. In analyzing an algorithm, we identify the important tasks the algorithm performs. Usually the number of times such tasks must be done in executing
the algorithm will depend on the size of the input. For example, searching a list of
n elements or sorting a list of n elements will require more work as n increases.
Typically, we can express input size as a nonnegative integer, so the functions that
express the amount of work will be functions with domain N. We found in Section
3.3 that a sequential search of n elements requires n comparisons in the worst case,
while a binary search requires 1 + log n comparisons in the worst case (assuming
n is a power of 2). Rather than compute the exact functions for the amount of work
Section 5.5 Order of Magnitude
415
x
h(x) = x 2
f (x) = x
c 2 h(x)
c 1 h(x)
Figure 5.28
If we imagine functions representing various forms of transportation, then
functions that are the same order of magnitude (belong to the same equivalence
class) represent the same mode of transportation. One class represents travel on
foot, another class represents travel by automobile, a third represents travel by air.
Speeds within a given mode are about the same; ignoring coefficients and loworder terms amounts to ignoring the difference between walking and running or
between a Jeep and a Jaguar or between a Cessna and a Boeing 787. Walking (at
any speed) is distinctly different from driving, which is distinctly different from
flying.
We can imagine a hierarchy of orders of magnitude. For example, the class
Θ(x) is a lower order of magnitude than the class Θ(x)
2
because functions that are
Θ(x) eventually fall below functions that are Θ(x
2
). Also, the class Θ(log x) is a
lower order of magnitude than Θ(x) (see Exercise 15 at the end of this section). In
our transportation analogy, walking is slower than driving is slower than flying.
A sort of arithmetic can be developed using order of magnitude. For example,
if f 1 (x) = x and f 2 (x) = x
2
, then the function ( f 1 + f 2 )(x) = f 1 (x) + f 2 (x) 5
x + x
2
= Θ(x
2
). In general, if f 1 = Θ(g 1 ) and f 2 = Θ(g 2 ), then f 1 + f 2 5
Θ(max (g 1 , g 2 )) (see Exercise 8). When expressed in abbreviated form,
this leads to somewhat bizarre equations such as Θ(x) + Θ(x
2
) = Θ(x
2
) or
Θ(x
2
) + Θ(x
2
) = Θ(x
2
).
More on analysis of algorithms
Order of magnitude is important in analysis of algorithms, which we discussed in
Section 3.3. In analyzing an algorithm, we identify the important tasks the algorithm performs. Usually the number of times such tasks must be done in executing
the algorithm will depend on the size of the input. For example, searching a list of
n elements or sorting a list of n elements will require more work as n increases.
Typically, we can express input size as a nonnegative integer, so the functions that
express the amount of work will be functions with domain N. We found in Section
3.3 that a sequential search of n elements requires n comparisons in the worst case,
while a binary search requires 1 + log n comparisons in the worst case (assuming
n is a power of 2). Rather than compute the exact functions for the amount of work