Al and Bill are arguing about the performance of their sorting algorithms. Al claims that his O(N log N)-time algorithm is always faster than Bill's O(N2)-time algo- rithm. To settle the issue, they implement and run the two algorithms on many randomly generated data sets. To Al's dismay, they find that if N 〈 1000 the O(N2)- time algorithm actually runs faster, and only when N 〉 1000 the 0(N logN)-time (10 pts.) one is better. Explain why the above scenario is possible

See in Explanation

Explanation:

All you know is that an algorithm is eventually (a lot) faster than an algorithm, but for any specific value of n, you can't say anything. Indeed, the asymptotic growth of the function doesn't depend on its value on . This means that if   then for all , the following function is also :

So asymptotic notation is completely uninformative regarding the performance of algorithms on specific values of n.

You could say that functions such as are artificial and never really occur in practice. This is not quite true (you can hard-code some auxiliary information for small n, for example), but even if you consider "natural" functions, asymptotic notation doesn't help you to determine anything other than asymptotic's: consider for example against (such examples definitely happen in practice, for example in fast matrix multiplication).