Codexon

Thanks to Donald Knuth, CS students and programmers know about Big O notation.

Unfortunately with all the years of academic brainwashing or glossing over, people think that Big O is all that matters and look at you funny if you dare to even mention substandard algorithms like linear search.

Formal Definition of Big O

Many people forget that M and X₀ can make a big difference.

Big O does not care about anything before Xo

Xo can also be large to the point of impracticality.

M can be huge, and the Big O will be the same for both algorithms.

A very interesting example of this in academia is this paper: Chazelle B., Triangulating a simple polygon in linear time.

The overhead for this method is so large that many prefer to use n log log n algorithms. A less exotic and glamourous example can be found in linear search vs binary search.

Credits: Joe Forker. Original benchmark: Alex Martelli.

As you can see here (or maybe not since its all blue), binary search begins to overcome linear search at around 130-150 integer elements. The program was written in C++ and run on a Pentium 4.

Related posts:

1. A Browser is not a Search Engine
2. A Bigger Hard Drive Is Not Always Faster
3. Hash Functions: the modulo prime myth?
4. Morton Codes
5. Fun with Facebook Graph