Al and Bob are arguing about their algorithms. Al claims his O(nlogn)- time method is always faster than Bob's O(n^2 )- time method. To settle the issue, they perform a set of experiments. To Al's dismay, they , find that if n=100 is the O(nlogn)-time one better.Explain how this is possible?

Question

Al and Bob are arguing about their algorithms. Al  claims his O(nlogn)- time method is always faster than Bob's O(n^2 )- time method. To settle the issue, they perform a set of experiments. To Al's dismay, they , find that if n<100 the O(n^2)-time algorithm runs faster, and only when n>=100 is the O(nlogn)-time one better.Explain how this is possible?

anonymous · Answer

Big O complexity is in reference to the worst possible growth rate of the algorithm. So O(N log N) means that it will never run in some time worse than O(N log N). So although Al's algorithm scales better than Bob's quadratic algo, it does not necessarily mean it is better for ALL input sizes. 

Perhaps there is significant overhead in establishing it such as creating a large amount of arrays or variables. Keep in mind that even an O(N log N) algorithm could have 1000 non nested loops that executive at O(N) and still be considered O(N log N) as long as it is the worst part.