Good text on algorithm complexity

Question

Where should I look for a good introductory text in algorithm complexity? So far, I have had an Algorithms class, and several language classes, but nothing with a theoretical backbone. I get the whole complexity, but sometimes it's hard for me to differentiate between O(1) and O(n) plus there's the whole theta notation and all that, basic explanation of P=NP and simple algorithms, tractability. I want a text that covers all that, and that doesn't require a heavy mathematical background, or something that can be read through.

LE: I'm still in highschool, not in University, and by heavy mathematical background I mean something perhaps not very high above Calculus and Linear Algebra (it's not that I can't understand it, it's the fact that for example learning Taylor series without having done Calculus I is a bit of a stretch; that's what I meant by not mathematically heavy. Something in which the math, with a normal amount of effort can be understood). And, do pardon if I'm wrong, but theoretically speaking, a class at which they teach algorithm design methods and actual algorithms should be called an "Algorithms" class, don't you think? In terms of my current understanding, infinite series, limits and integrals I know (most of the complexity books I've glanced at seemed to use those concepts), but you've lost me at the Fast Fourier Transform.

Answer 1

It is my very personal opinion that the book of Jon Kleinberg and Éva Tardos is the best book for studying the design and analysis of efficient algorithms. It might be not as comprehensive as Cormen et al. but it is a great textbook. Let me point out, why I think this book might suit your interests best

• you don't need heavy math machinery for the proofs
• the book gives often a great intuition why something is working (or not), this is in my opinion very important for beginners and self learners
• a very intuitive approach to NP-completeness
• it has a great chapter how to deal with NP-complete problems in practice
• it focuses on design patterns, which might help you to design your own clever algorithms

You should also notice, that there is a lot of free material in the WWW available. Great lecture notes are provided by Jeff Erickson. And you can even watch the whole MIT class on "Introductions to algorithms" taught by Charles Leiserson and Erik D. Demaine. Cool stuff!

Answer 2

You can surely bet for the famous book of Cormen et al. "Introduction To Algorithms". First of all it's quite difficult to understand the book if you don't have sound mathematical base. But for the shake of easy understanding you can skip those mathematical proofs (not recommended). Also you can go for Algorithm Design Manual.

Answer 3

You should have a look at M. Sipser's "Introduction to the Theory of Computation". I did read (and understood) this book when I was in High School, so I think it is suitable for you.

Although it's quite formal, everything is also explained in plain English. It also has a little introduction to proof techniques at the beginning.

---

Note: If you want to do CS on a serious level (e.g. research) you need a solid background in math. There is no short cut. Have a look at i.e. Graham, Knuth and Patashnik's Concrete Mathematics.