Cover by Gary Pollice, Stanley Selkow, George T. Heineman

Safari, the world’s most comprehensive technology and business learning platform.

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required

O'Reilly logo

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 ...

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required