This article has way too many words and not enough math. There is, in fact, nothing scary about big O notation once you dissect it, and it's a shame that so many people seem to think otherwise.<p>Here's the definition: if f and g are functions (let's say real-valued functions defined on the positive reals), then we say that f is <i>big O of g</i>, written f = O(g), if there exists a real number y and a real number K, K > 0, such that<p><pre><code> f(x) <= K * g(x)
</code></pre>
for every x > y.<p>If that makes sense, then done.<p>Else:<p>The first thing to do when meeting any mathematical definition that you don't understand is to throw away parts of the definition until you do understand it, then add them back in one by one. In this case, let's forget about the constant.<p><i>New definition</i>: For functions f, g, f is <i>blorb of g</i>, denoted f = blorb(g), if there is a y such that<p><pre><code> f(x) <= g(x)
</code></pre>
for every x > y.<p>"f is blorb of g" actually just means that there comes a point after which g is never smaller than f. This gives us the first ingredient of big O: we are concerned only with asymptotic behavior. f could take on immense values for small x and still be O(g) as long as f eventually becomes always smaller than g.<p>The reason for caring about asymptotic behavior is that we often don't care about the time complexity of an algorithm for very small problem sizes. Even the traveling salesman problem is solvable on Raspberry Pi for very small problem sizes.<p>Okay, I hope we understand the above definition. Now we add the constant back into the fold and see if we can make sense of it. From what I can see, the constant is there for computer scientists who want to paint with broader strokes. There can be a huge practical difference between f1(n) = 2n and f2(n) = 2000n (the difference between a computation taking a day and taking 3 years), but they're both O(n) because complexity theorists are more concerned with O(n^2) versus O(2^n) than they are with O(n) versus O(5n). (Also could be because in practice algorithms with wildly varying constant factors out in front are rarely seen?)<p>For an alternative to big O notation, you should check out Sedgewick and Wayne's Algorithms, 4th ed. They use something they call "tilde notation" which preserves the leading constant factor. (See: <a href="http://introcs.cs.princeton.edu/java/41analysis/" rel="nofollow">http://introcs.cs.princeton.edu/java/41analysis/</a>)