Info on the big-O notation

[Graeme]

Hi,

Has anybody got a good URL or document or summary email that explains the big-O notation? It is often used to describe a task/method/algorithm to say how quick or efficient it runs, or how well coded your method might be. I kind-of have an idea how it works, but I would really like to solidify my knowledge of it.

An example usage would be something like:
  There are multiple ways to implement a "find the longest palindrome"
  function. A simple solution would result in O(n^2) runtime, and a well
  optimised solution would produce a O(n) runtime.


Regards,
  Graeme

[marcov]

As you probably know, basically it is how the worst case computing time increases with the number of elements rising, with the idea that for infinite N, the algorithm with the lowest magnitude always wins out.

The basic analysis is just taking the dominant (highest power, fastest growing) of an expression and removing constants and lesser terms.   So O(5*x^2 + 40*x+53)  becomes O(X^2)

For more complex algorithms the magnitude can be found in literature e.g. Knuth or the many books of Sedgewick. Sedgewick's "analysis of algorithms" is probably also a good source for this kind of stuff.

There are also some cautions:

• For not infinite sets, constants might still be important
• Memory is not uniform due to caching. This can reduce O (x^2) to O(x) in practice if the quadratic access is strictly with the element next to it

[Graeme]

Thank you Marco for your reply.

In the mean time I did yet more Internet searching and came across the following URL that gives an excellent explanation with graphs and simple sample code.

  http://cooervo.github.io/Algorithms-DataStructures-BigONotation/big-O-notation.html

Now finally it makes more sense to me. 

[Leledumbo]

The wikipedia article is more than sufficient, albeit maybe a bit too complex to easily understand, but try reading it to get a deeper understanding. It's full of examples as well while also introduces other family members such as big/small omega & theta, even if people are mostly interested in the big O.