Complexity in Computer Science

by Thomas Watson

to be published by Cambridge University Press

Computational complexity theory is about the fundamental capabilities and limitations of efficient computation. Framing the subject in the broader context of computer science, this textbook is both a self-contained tutorial for general computer science students and a thorough reference for specialists. Using only elementary discrete math, the book rigorously covers the central concepts of time, space, and randomness in computing, as well as connections to other areas of computer science such as cryptography and machine learning. Intuitions and general techniques are emphasized. The book features full proofs, numerous concrete examples and illustrations, and hundreds of exercises.

---

Full book:	Supplement:
Complexity in Computer Science	Discrete Math Background
Solutions to Exercises	Solutions to Exercises
Table of Contents and Preface

This material will be published by Cambridge University Press as Complexity in Computer Science by Thomas Watson. This prepublication version is free to view and download for personal use only. Not for re-distribution, re-sale, or use in derivative works.

© Thomas Watson, 2026.

Please send corrections to: Thomas.Watson@memphis.edu

---