[Solved]: Good text on algorithm complexity

Problem Detail: 

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.

Asked By : andreas.vitikan

Answered By : A.Schulz

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!

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3201