# Good text on algorithm complexity

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.

• Covering all that in a "backbone" manner without maths? Huh. Maybe you'll find something here or here. Regarding Landau notation, maybe this helps. Other than that, does your university not offer better courses? O.o (Sorry, I don't know many basic English books.) Note that questions of this form tend to work badly on the SE platform, so don't be surprised if it gets downvoted or closed.
– Raphael
Aug 15 '12 at 20:00

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