News for hackers. Stuff that matters.
Re:Big-O notation explained by a self-taught programmer by kyllo on Friday July 26, 2013 @08:23PM (#6111309)
* That constant may be so large that an O(N^2) may be a better solution for any practical purpose.*

Another example of this is that a good system/library sorting function will sometimes use an asymptotically fast algorithm like quicksort or mergesort only for arrays over a certain size, but will switch over to a O(n^2) algorithm like insertion sort to sort smaller arrays, because it has smaller constants and coefficients. (But sometimes this is overkill, because if n is small, you probably aren't going to notice the speed difference anyway.)

So yes, Big O is all about asymptotic behavior, which basically means, the rate of growth as n approaches infinity. Because a large value of n is when the choice of algorithm starts to really matter for performance.

There are no comments on this comment yet.