Algorithms in a Nutshell

Chapter 2. The Mathematics of Algorithms

In choosing an algorithm to solve a problem, you are trying to predict which algorithm will be fastest for a particular data set on a particular platform (or family of platforms). Characterizing the expected computation time of an algorithm is inherently a mathematical process. In this chapter we present the mathematical tools behind this prediction of time. Readers will be able to understand the various mathematical terms throughout this book after reading this chapter.

A common theme throughout this chapter (and indeed throughout the entire book) is that all assumptions and approximations may be off by a constant, and ultimately our abstraction will ignore these constants. For all algorithms covered in this book, the constants are small for virtually all platforms.

Size of a Problem Instance

An instance of a problem is a particular input data set to which a program is applied. In most problems, the execution time of a program increases with the size of the encoding of the instance being solved. At the same time, overly compact representations (possibly using compression techniques) may unnecessarily slow down the execution of a program. It is surprisingly difficult to define the optimal way to encode an instance because problems occur in the real world and must be translated into an appropriate machine representation to be solved on a computer. Consider the two encodings shown in the upcoming sidebar, "Instances Are Encoded," for a number ...