Java Reference
In-Depth Information
it is in (h(n)). Note that we drop the word “in” for notation, because there
is a strict equality for two equations with the same . In other words, if f(n) is
(g(n)), then g(n) is (f(n)).
Because the sequential search algorithm is both in O(n) and in (n) in the
average case, we say it is (n) in the average case.
Given an algebraic equation describing the time requirement for an algorithm,
the upper and lower bounds always meet. That is because in some sense we have
a perfect analysis for the algorithm, embodied by the running-time equation. For
many algorithms (or their instantiations as programs), it is easy to come up with
the equation that defines their runtime behavior. Most algorithms presented in this
book are well understood and we can almost always give a analysis for them.
However, Chapter 17 discusses a whole class of algorithms for which we have no
analysis, just some unsatisfying big-Oh and analyses. Exercise 3.14 presents
a short, simple program fragment for which nobody currently knows the true upper
or lower bounds.
While some textbooks and programmers will casually say that an algorithm is
“order of” or “big-Oh” of some cost function, it is generally better to use notation
rather than big-Oh notation whenever we have sufficient knowledge about an alg-
orithm to be sure that the upper and lower bounds indeed match. Throughout this
book, notation will be used in preference to big-Oh notation whenever our state
of knowledge makes that possible. Limitations on our ability to analyze certain
algorithms may require use of big-Oh or notations. In rare occasions when the
discussion is explicitly about the upper or lower bound of a problem or algorithm,
the corresponding notation will be used in preference to notation.
3.4.4
Simplifying Rules
Once you determine the running-time equation for an algorithm, it really is a simple
matter to derive the big-Oh, , and expressions from the equation. You do not
need to resort to the formal definitions of asymptotic analysis. Instead, you can use
the following rules to determine the simplest form.
1. If f(n) is in O(g(n)) and g(n) is in O(h(n)), then f(n) is in O(h(n)).
2. If f(n) is in O(kg(n)) for any constant k > 0, then f(n) is in O(g(n)).
3. If f
1
(n) is in O(g
1
(n)) and f
2
(n) is in O(g
2
(n)), then f
1
(n) + f
2
(n) is in
O(max(g
1
(n);g
2
(n))).
4. If f
1
(n) is in O(g
1
(n)) and f
2
(n) is in O(g
2
(n)), then f
1
(n)f
2
(n) is in
O(g
1
(n)g
2
(n)).
The first rule says that if some function g(n) is an upper bound for your cost
function, then any upper bound for g(n) is also an upper bound for your cost func-
tion. A similar property holds true for notation: If g(n) is a lower bound for your
