Recommended Complexity Theory Book(s)

Question

I'd like to start off by saying that I have no formal training in computer science. I have several years of programming experience but I'm entirely self-taught. Additionally, I have a relatively good grasp of common algorithms and their performance (e.g., time vs. space) characteristics.

Since I lack formal training, however, I feel like I might (and most likely do) have knowledge gaps when it comes to this subject (and others, of course).

I would therefore sincerely appreciate any book recommendations that cover this subject from a beginners* point of view.

NOTE: I realize that this question is a little subjective, but I really don't know of any other community with such a prevalent level of expertise among the member population; hence my asking here.

---

*I'd like to [re-]start from the basics to make sure I understand all the fundamentals.

Answer 1

This may not be applicable to your problem domain, but for scientific computing, the classic Numerical Recipes includes discussion of time/space complexity in a very practical vein (as well as discussion precision, numerical stability, et al) and is very smart-beginner accessible.

It is, however, not a general treatment of the field of time/space complexity.

Answer 2

For an intro, if you know c++ (or want to learn) I'd suggest Sedgewick's Algorithms in C++

He also has a Java version

These two are great, but slightly heavy:

• CLRS (the algorithms bible, should be on every programmer's bookshelf)
• Computers and Intractability: A Guide to the Theory of NP-Completeness

Answer 3

I recommend Programming Pearls. It doesn't have the math rigor of academic texts, and it is not solely dedicated to algorithm analysis, but it is a classic text and written by a master. It may not satisfy your goal, but it is a very good bridge to other texts, and you'll be a better developer after working through it.

Answer 4

A very good book about introduction (and more) to algorithm:

Introduction to Algorithms By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

I have worked with this book at my university to learn algorithm and It's very interesting to learn basis of algorithm and to start to study it in depth.

Answer 5

Algorithmics by David Harel. This has the best and most clear discussion of complexity, problem classes, and NP-Completeness of any text I've found. Often overlooked, extremely accessible, and an essential text before plunging into Cormen, especially for those without formal CS training.