s
Section 5.5 Order of Magnitude
413
Given that r is an equivalence relation, it partitions S into equivalence classes.
If f is in the same class as g, then f is said to have the same order of magnitude as g,
denoted by f = Θ(g) and pronounced “f is order g” or sometimes “f is big theta of
g.” Because of symmetry, this also means that g is the same order of magnitude as
f, or g = Θ( f ). (The notation f = Θ(g) is a bit of a misuse of the equality symbol
because Θ(g) is not some function identical to f. It is just a shorthand way of saying that f [ 3g 4 under the equivalence relation r defined above.)
example 44
Let f and g be functions in S where f(x) = 3x
2
and g(x) = 200x
2
+ 140x + 7
Let n 0 = 2, c 1 =
1
100
, and c 2 = 1. Then for x ≥ 2,
1
100
(200x
2
+ 140x + 7) ≤ 3x
2
≤ (1)(200x
2
+ 140x + 7)
or
2x
2
+ 1.4x + 0.07 ≤ 3x
2
≤ 200x
2
+ 140x + 7
(1)
Therefore f r g.
PRaCtiCe 40
a. Verify the inequality in Equation (1) for the following values of x: 2, 3, 4, 5. (Use a calculator.)
b. In Example 44, can n 0 have the value 1 if c 1 and c 2 remain the same?
c. Find a different set of three values n 0 , c 1 , and c 2 that will also work to show that f r g in
Example 44.
■
The relation r is an equivalence relation on S. For example, to prove that
f r f , we can pick n 0 = c 1 = c 2 = 1 and have
(1) f (x) ≤ f (x) ≤ (1) f (x)
PRaCtiCe 41
a. Prove that r is symmetric.
b. Prove that r is transitive.
■
DefInItIon oRdeR oF Magnitude
Let f and g be functions mapping nonnegative reals into nonnegative reals. Then
f is the same order of magnitude as g, written f = Θ(g), if there exist positive
constants n 0 , c 1 , and c 2 such that for x ≥ n 0 , c 1 g (x) ≤ f (x) ≤ c 2 g (x).