Resource on computational time complexity of algorithms

Question

Is there a good resource (book, link, website, application ...) that explains how to calculate the time complexity of the algorithm?

Because it’s hard to make things concrete in my mind. Sometimes it is an iteration with time complexity lg n; and then according to another loop it becomes n.lg n; and sometimes they use large omega designations to express it, sometimes large-o, etc.

These things are pretty abstract to me. So, I need a resource that has a good explanation and lots of examples to make me see what happens.

I hope I clearly explained my problem. I am quite sure that everyone who has just started to learn algorithms also have the same problem with me. Thus, it is possible that these experienced guys can also share their experience with us. Thanks...

Answer 1

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

Here on Amazon .

Answer 2

You guys all recommend complexity theory books - Arora and Barak contain all kinds of things like PCP, Interactive Proofs, Quantum Computing and topics on Expander graphs - something that most programmers / software developers have never heard of or will ever have. be used. Papdimitriou is in the same category. Knut has nothing to read (and I was the main mathematician in CS / Math) and gives zero intuition about how everything works.

If you want a simple way to calculate battery life and get a taste of analysis, try the first chapter or so of Kleinberg and Tardos, “Design and Analysis of Algorithms,” which holds your hand through the basics, and then you can work on much more complex problems.

Answer 3

I read Christos Papadimitriou Computational Complexity at the University and really enjoyed it. This is not easy, the book is long, but it is well written (that is, understandable and suitable for self-study), and it contains a lot of useful knowledge, much more than just “how to determine the time complexity of algorithm x”.

Answer 4

I agree that Introduction to Algorithms is a good book. For more detailed instructions, for example. how to solve recurrence relationships see Knuth Concrete Mathematics . A good book on computational complexity itself is Papadimitriou . But this last book may be too thorough if you want to calculate the complexity of these algorithms.

A brief overview of the meaning of large O / -Omega:

• If you can give an algorithm that solves the time problem T (c * (n log n)) (c is a constant), then the time complexity of this problem is O (n log n). Big-O gets rid of c, that is, any constant factors independent of input size n. Big-O gives an upper bound during runtime because you showed (by providing an algorithm) that you can solve the problem in that period of time.
• If you can give proof that any algorithm that solves the problem takes at least T (c * (n log n)) time than the problem in Omega (n log n). Big-Omega gives a lower bound on the problem. In most cases, lower bounds are much more difficult to prove than upper bounds, because you must show that any possible algorithm for the problem takes at least T (c * (n log n). Knowing the lower bound does not mean knowing the algorithm that reaches this lower bound borders.
• If you have a lower bound, for example. Omega (n log n), and an algorithm that solves the problem during this time (upper bound) than the problem in Theta (n log n). This means that the “optimal” algorithm for this problem is known. Of course, this notation hides a constant factor c, which can be quite large (so I wrote the optimal value in quotation marks).

Please note that when using these notations, you usually talk about the worst running time of the algorithm.

Answer 5

Computational complexity theory on Wikipedia has a list of links, including a link to a draft book, “Computational Complexity: A Modern Approach,” by Sanjeev Arora and Boaz Barak, Press Cambridge University Press.

Answer 6

A classic set of books on this subject is Knuth Art of Computer Programming . They are difficult in theory and formal evidence, so clear your calculus before embarking on them.

Answer 7

A course in Discrete Mathematics is sometimes provided before Introduction to Algorithms .