What this Book Is About

The complexity of an algorithm is the cost, measured in running time, or storage, or whatever units are relevant, of using the algorithm to solve one of those problems. This book is about algorithms and complexity, and so it is about methods for solving problems on computers and the costs (usually the running time) of using those methods. For the purposes of the book, a computation that is guaranteed to take at most cn³ time for input of size n will be thought of as an ‘easy’ computation. The general rule is that if the running time is at most a polynomial function of the amount of input data, then the calculation is an easy one, otherwise it’s hard. The book deals with some easy problems and some seemingly hard ones. The seemingly hard problems are those for which no one has found a fast computer algorithm, but also, no one has proved the impossibility of doing so.