Java Reference
In-Depth Information
3.12
Further Reading
Pioneering works on algorithm analysis include The Art of Computer Programming
by Donald E. Knuth [Knu97, Knu98], and The Design and Analysis of Computer
Algorithms by Aho, Hopcroft, and Ullman [AHU74]. The alternate definition for
comes from [AHU83]. The use of the notation “T(n) is in O(f(n))” rather
than the more commonly used “T(n) = O(f(n))” I derive from Brassard and
Bratley [BB96], though certainly this use predates them. A good book to read for
further information on algorithm analysis techniques is Compared to What?
by
Gregory J.E. Rawlins [Raw92].
Bentley [Ben88] describes one problem in numerical analysis for which, be-
tween 1945 and 1988, the complexity of the best known algorithm had decreased
from O(n 7 ) to O(n 3 ). For a problem of size n = 64, this is roughly equivalent
to the speedup achieved from all advances in computer hardware during the same
time period.
While the most important aspect of program efficiency is the algorithm, much
improvement can be gained from efficient coding of a program. As cited by Freder-
ick P. Brooks in The Mythical Man-Month [Bro95], an efficient programmer can of-
ten produce programs that run five times faster than an inefficient programmer, even
when neither takes special efforts to speed up their code. For excellent and enjoy-
able essays on improving your coding efficiency, and ways to speed up your code
when it really matters, see the topics by Jon Bentley [Ben82, Ben00, Ben88]. The
situation described in Example 3.18 arose when we were working on the project
reported on in [SU92].
As an interesting aside, writing a correct binary search algorithm is not easy.
Knuth [Knu98] notes that while the first binary search was published in 1946, the
first bug-free algorithm was not published until 1962! Bentley (“Writing Correct
Programs” in [Ben00]) has found that 90% of the computer professionals he tested
could not write a bug-free binary search in two hours.
Search WWH ::




Custom Search