Resource on computing time complexity of algorithms [closed]

Question

Is there any good resource (book, reference, web site, application...) which explains how to compute time complexity of an algorithm?

Because, it is hard to make the things concrete in my mind. Sometimes it is talking about an iteration has time complexity of lg n; and then according to the another loop it becomes n.lg n; and sometimes they use big omega notation to express it, sometimes big-o and etc...

These things are quite abstract to me. So, I need a resource which has good explanation and a lot of examples to make me see what's goin on.

Hopefully, I explained my problem clearly. I am quite sure that everyone who just started to study algorithms has also the same problem with me. So, maybe those experienced guys can also share their experience with us. Thanks...

Answer 1

I think the best book is Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein.

Here is it on Amazon.

Answer 2

Guys, you're all recommending true complexity theory books -- Arora and Barak contains all sorts of things like PCP, Interactive Proofs, Quantum Computing and topics on Expander graphs -- things that most programmers/software developers have never heard of or will ever use. Papdimitriou is in the same category. Knuth is freaking impossible to read (and I was a CS/Math major) and gives zero intuition on how things work.

If you want a simple way to compute runtimes, and to get the flavour of the analysis, try the first chapter or so of Kleinberg and Tardos "Design and Analysis of Algorithms", that holds your hand through the fundamentals, and then you can work on much harder problems.