In theory, there's no significant differences between theory and practice. In practice, things are never so simple. When you use Big-Oh notation, O(f(n)), you

In theory, there's no significant differences between theory and practice. In practice, things are never so simple. When you use Big-Oh notation, O(f(n)), you claim that there exist one function F(n) that accurately characterizes the running time of an algorithm based on the size of the input, and that f(n) is the higher order component of that function. I looks something like this: F(n) = A*f(n) + B*g(n) + C*h(n) + ... + K where A,B,C,..K are constants and f,g,h,... are functions. You approximate F(n) ~= Af(n) because for n big enough, this component will dominate the growth of such function. But A is different for different algorithms... so, in the case of sorting, you have several options - quicksort, mergesort, heapsort - that are in paper all "the same" but each has a different constant, and there are real advantages of using the one with the smallest constant. Furthermore, if you are not trying to sort infinitely big data (most real world cases) you must consider that other components of the actual F(n) function, such as g and h, may dominate the performance of the algorithm in the range of data sizes that you are more likely to encounter. There are other measures of algorithmic complexity that deal with this (I recall there is one Small-Oh notation, among others), but they don't teach you that at school unless you are a posgraduate student doing highly relevant work in complexity theory. I suspect most guys, like myself, find out by not taking Knuth as holy gospel and reading further material. And then there are the degenerate cases, where your data can get sorted in quasi-linear time if you apply one of the slow dumb O(n^2) dinosaurs.