Algorithms in a Nutshell

12

Chapter 2 The Math of Algorithms

2

The Mathematics of

Algorithms

In choosing an algorithm to solve a problem, you are trying to predict which algo-

rithm 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 unneces-

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

As much as possible, we want to evaluate algorithms by assuming that the

encoding of the problem instance is not the determining factor in whether the

algorithm can be implemented efficiently. Although the encodings are nearly iden-

tical in size, they offer different performance on the key operation, which

determines whetherx has an even or odd number of 1-bits in its binary

representation.

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use