s
Section 5.5 Order of Magnitude
417
Note that the exponential case grows at a fantastic rate! Even if we assume
that each computation step takes much less time than 0.0001 second, the relative
growth rates between polynomial and exponential functions still follow this same
pattern. Because of this immense growth rate, algorithms not of polynomial order
are generally not useful for large values of n. In fact, problems for which no polynomial time algorithms exist are called intractable.
Sometimes algorithms that are not polynomial in the worst case may still be
efficient for “average”—and useful—input cases.
2
Nonetheless, in attempting to improve efficiency, we should ask whether a different algorithm of a lower order of
magnitude exists before we worry about the details of fine-tuning a given algorithm.
If f (n) represents the work done by an algorithm on an input of size n, it may
be difficult to find a simple function g such that f = Θ(g). Remember that if we
can find such a g, then f and g are functions that eventually (for large enough n)
have roughly the same shape. But we may still be able to find a function g that
serves as an upper bound for f. In other words, while f may not have the same
shape as g, f will never grow significantly faster than g. Formally, this is expressed
by saying that f = O(g) (“f is big O of g”).
2 This is the case with the well-known simplex method for solving linear programming problems, which are a
generalization of systems of linear equations to systems of inequalities—see Section 5.7.
DefInItIon Big oH
Let f and g be functions mapping nonnegative reals into nonnegative reals. Then
f is big oh of g, written f = O(g), if there exist positive constants n 0 and c such
that for x ≥ n 0 , f (x) ≤ cg(x).
If f = O(g), then g is a ceiling for f and gives us a worst-case picture of the
growth of f. In Section 3.3, we learned that if E(n) is the number of divisions
required by the Euclidean algorithm to find gcd(a, b), where b < a = n, then
E(n) = O(log n)
The big oh notation f = O(g) says that f grows at the same rate or at a slower
rate than g. But if we know that f definitely grows at a slower rate than g, then we
can say something stronger, namely that f is little oh of g, written f = o(g). The
relationship between big oh and little oh is this: If f = O(g), then either f = Θ(g)
or f = o(g), much like a ≤ b says that either a = b or a < b.
the Master theorem
In Section 3.2, we learned that a solution for divide-and-conquer recurrence relations of the form
S(n) = cSa
n
2
b + g(n) for n ≥ 2, n = 2
m
is given by
S(n) = c
log n
S(1) + ∙
log n
i=1
c
(log n)−i
g(2
i
)
Section 5.5 Order of Magnitude
417
Note that the exponential case grows at a fantastic rate! Even if we assume
that each computation step takes much less time than 0.0001 second, the relative
growth rates between polynomial and exponential functions still follow this same
pattern. Because of this immense growth rate, algorithms not of polynomial order
are generally not useful for large values of n. In fact, problems for which no polynomial time algorithms exist are called intractable.
Sometimes algorithms that are not polynomial in the worst case may still be
efficient for “average”—and useful—input cases.
2
Nonetheless, in attempting to improve efficiency, we should ask whether a different algorithm of a lower order of
magnitude exists before we worry about the details of fine-tuning a given algorithm.
If f (n) represents the work done by an algorithm on an input of size n, it may
be difficult to find a simple function g such that f = Θ(g). Remember that if we
can find such a g, then f and g are functions that eventually (for large enough n)
have roughly the same shape. But we may still be able to find a function g that
serves as an upper bound for f. In other words, while f may not have the same
shape as g, f will never grow significantly faster than g. Formally, this is expressed
by saying that f = O(g) (“f is big O of g”).
2 This is the case with the well-known simplex method for solving linear programming problems, which are a
generalization of systems of linear equations to systems of inequalities—see Section 5.7.
DefInItIon Big oH
Let f and g be functions mapping nonnegative reals into nonnegative reals. Then
f is big oh of g, written f = O(g), if there exist positive constants n 0 and c such
that for x ≥ n 0 , f (x) ≤ cg(x).
If f = O(g), then g is a ceiling for f and gives us a worst-case picture of the
growth of f. In Section 3.3, we learned that if E(n) is the number of divisions
required by the Euclidean algorithm to find gcd(a, b), where b < a = n, then
E(n) = O(log n)
The big oh notation f = O(g) says that f grows at the same rate or at a slower
rate than g. But if we know that f definitely grows at a slower rate than g, then we
can say something stronger, namely that f is little oh of g, written f = o(g). The
relationship between big oh and little oh is this: If f = O(g), then either f = Θ(g)
or f = o(g), much like a ≤ b says that either a = b or a < b.
the Master theorem
In Section 3.2, we learned that a solution for divide-and-conquer recurrence relations of the form
S(n) = cSa
n
2
b + g(n) for n ≥ 2, n = 2
m
is given by
S(n) = c
log n
S(1) + ∙
log n
i=1
c
(log n)−i
g(2
i
)