This book consists of two parts, one dealing with computational complexity of sequential algorithms and the other describing computational complexity of parallel algorithms. In many instances, both sequential and parallel algorithms for the same class of problems are treated. Most of the important results from the theory and applications of the sequential algorithms are included, whereas for parallel algorithms, major developments and existing notions in this fast developing area are described.

In the sequential algorithms category, the topics discussed are Arithmetic Complexity of Computations, Worst and Average Case Complexities of Data Processing Algorithms, Combinatorial Problems, Theorem Proving by Machines, Theory of Computational Complexity, and Complexity Classes. Practical applications of many algorithms are given throughout the text, such as the application of the FFT algorithm in the CAT Scanner. Both well-known and not so well-known classes of complexity are described, e.g., P, NP, NP-Complete, #P-Complete (problems that are apparently intractable to compute), CO-NP (problems that are complements of some problems in NP and typically of the form, “show that there are no solutions”), etc.

The discussion on parallel algorithms begins with a brief description of various computer architectures that are relevant to understanding parallel algorithms. The topics covered are Root Finding Algorithms for Non-linear Functions, Iterative Parallel Algorithms, Matrix Multiplication Algorithms, Parallel FFT Algorithm, Sorting Algorithms, and Graph Search and Traversal Algorithms. Many models to analyze parallel algorithms are discussed.

One of the real strengths of this book is the thorough discussion of all major work related to the topics covered. Results from scientists in the West as well as in the East are included and appropriately referenced. The lead-in text for each topic is very well written and should help motivate the readers.

The author claims that the book can be used by second- and third-year undergraduate students, as well as by postgraduate students in mathematics, computer science, and software engineering. I believe that the book can be used for fourth-year (senior) undergraduate and postgraduate students in mathematics and computer science.