StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I agree that <a href="http://projects.csail.mit.edu/clrs/" rel="nofollow noreferrer">Introduction to Algorithms</a> is a good book. For more detailed instructions on e.g. how to solve recurrence relations see Knuth's <a href="http://en.wikipedia.org/wiki/Concrete_Mathematics" rel="nofollow noreferrer">Concrete Mathematics</a>. A good book on Computational Complexity itself is the one by <a href="http://books.google.com/books?id=HuWVGgAACAAJ&dq=Papadimitriou+complexity&ei=cimGSZH1FqTmyASzzLinDQ" rel="nofollow noreferrer">Papadimitriou</a>. But that last book might be a bit too thorough if you only want to calculate the complexity of given algorithms.</p> <p>A short overview about big-O/-Omega notation:</p> <ul> <li>If you can give an algorithm that solves a problem in time <em>T(c*(n log n))</em> (<em>c</em> being a constant), than the time complexity of that problem is <em>O(n log n)</em>. The big-O gets rid of the <em>c</em>, that is any constant factors not depending on the input size <em>n</em>. Big-O gives an <strong>upper bound</strong> on the running time, because you have shown (by giving an algorithm) that you can solve the problem in that amount of time.</li> <li>If you can give a proof that any algorithm solving the problem takes at least time <em>T(c*(n log n))</em> than the problem is in <em>Omega(n log n)</em>. Big-Omega gives a <strong>lower bound</strong> on the problem. In most cases lower bounds are much harder to proof than upper bounds, because you have to show that any possible algorithm for the problem takes at least <em>T(c*(n log n)</em>. Knowing a lower bound does <strong>not</strong> mean knowing an algorithm that reaches that lower bound.</li> <li>If you have a lower bound, e.g. <em>Omega(n log n)</em>, <strong>and</strong> an algorithm that solves the problem in that time (an upper bound), than the problem is in <em>Theta(n log n)</em>. This means an "optimal" algorithm for this problem is known. Of course this notation hides the constant factor <em>c</em> which can be quite big (that's why I wrote optimal in quotes).</li> </ul> <p>Note that when using these notations you are usually talking about the worst-case running time of an algorithm.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload