But (and that's a pretty big but), 'Big O' is not all there is, and once you've picked your algorithm based on the one that has the best expected runtime based on 'Big O', you really have to try to make sure that:
- your algorithm is executed with the lowest possible frequency
- you concentrate on those pesky n's that you eliminated during analysis to
make sure that you don't end up wasting all your CPU time on some
little detail somewhere
- you take in to account the effects of your code on caches and virtual memory
- you profile your code afterwards to make sure that all your assumptions regarding
the above are correct
So if you are going to optimize, do it on the basis of cold empirical data, not intuition.
Even though Winograd's algorithm (matrix multiplication) is theoretically faster than Strassen's, the constant is so high that Winograd's is only faster in matrices so large you can't practically compute in the first place.
Quicksort is a more familiar example. Although its worst case complexity is O(n^2), many techniques have been invented to avoid the worst cases and execute in just O(n log n) (average case), and it's usually faster than merge sort in practice.
I don't consider this a limitation of big O notation at all, but rather a common misconception among students when they first learn about the notation.
If all values in your set of numbers to sort are unique, then quicksort is indeed O(n lg n) worst case if you pivot about the median. If there are duplicate values, can you think of a way to still guarantee worst case O(n lg n)?
Big O is a tool for making estimates, and like all other (such) tools, you have to know its limitations to use it properly.
Err, no it doesn't. Big O is a tool for saying how quickly an algorithm runs based on the size of n, and it's usually used to measure real things, like what will happen when the filesystem has to handle 100,000 files, then 1,000,000, etc.
More precisly, it tells how the relative speed difference between 2 algorithms change when n goes to toward infinity. An O(n) will win over O(n^2), but the latter case might have a huge constant factor that makes it slower than the former for e.g. n <= million.
And very often, n is smaller than a million.
Big O notation, or Landau notation, is not just O(g(n)). It's also o(), Ω(), ω() and Θ(). It's understood, though, that n is considered to usually be rather large - another name for this notation is, after all, "asymptotic notation." In any case that you're really worried about speed, you should probably be calculating the speed of your algorithm directly rather than using mere asymptotic generalizations.
Aside: I can't think of any algorithms with huge constants like you described; in theory, you're correct, but in practice, the asymptotic generalizations apply for n <= 1000 or even often 100.
Make sure what n is in each case. For example a graph algorithm with O(n^2) and n being the number of nodes may actually be O(n) for n being the graph size (number of edges).
Was it a dream? A computer simulation? An alternate reality? I mean, really, wtf?