Algorithms in a Nutshell

Principle: Support Mathematical Analysis Empirically

We mathematically analyze the performance of each algorithm in this book to help programmers understand the conditions under which each algorithm performs at its best. We provide live code examples, and in the accompanying code repository there are numerous JUnit (http://sourceforge.net/projects/junit) test cases to document the proper implementation of each algorithm. We generate benchmark performance data to provide empirical evidence regarding the performance of each algorithm.

We classify each algorithm into a specific performance family and provide benchmark data showing the execution performance to support the analysis. We avoid algorithms that are interesting only to the mathematical algorithmic designer trying to prove that an approach performs better at the expense of being impossible to implement. We execute our algorithms on a variety of programming platforms to demonstrate that the design of the algorithm—not the underlying platform—is the driving factor in efficiency.

The appendix contains the full details of our approach toward benchmarking, and can be used to independently validate the performance results we describe in this book. The advice we give you is common in the open source community: "Your mileage may vary." Although you won't be able to duplicate our results exactly, you will be able to verify the trends that we document, and we encourage you to use the same empirical approach when deciding upon algorithms ...