<story><title>Big-O notation explained by a self-taught programmer</title><url>http://justin.abrah.ms/computer-science/big-o-notation-explained.html</url></story><parent_chain></parent_chain><comment><author>YZF</author><text>The math of Big-O isn&amp;#x27;t that hard and the article while having good intentions misses the point.  Big-O is about asymptotic behaviour and the graphs are misleading in that regard (well, they&amp;#x27;re simply wrong, not misleading).  There are algorithms where if you just look at the Big-O you&amp;#x27;d think one has faster run time than the other but because the constants fall out that wouldn&amp;#x27;t be the case for any practical problem size.&lt;p&gt;What O(N) means is there is some large enough number where the run-time (edit: or any function really) is bounded by a constant times the input size for any input size larger than that number (see, math, not hard).  That constant may be so large that an O(N^2) may be a better solution for any practical purpose.&lt;p&gt;EDIT: As an example of this we can look at two multiplication algorithms, Karatsuba and Schönhage–Strassen, the latter having better asymptotic performance but that really kicks in once you have large enough numbers (100,000 digits or so). ( &lt;a href=&quot;http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Sch%C3%B6nhage%E2%80%93Strassen...&lt;/a&gt; )</text></comment>
<story><title>Big-O notation explained by a self-taught programmer</title><url>http://justin.abrah.ms/computer-science/big-o-notation-explained.html</url></story><parent_chain></parent_chain><comment><author>yid</author><text>Unfortunately, there are some misconceptions that are propagated in this article. Kudos on the effort, but some statements are just flat out wrong, such as this statement: &amp;quot;Big-O is all about the approximate worst-case performance&amp;quot;. Big-O has nothing to do with worst-case, but is a &lt;i&gt;bounding&lt;/i&gt; function. An O(n) algorithm is also O(n^2), O(2^n), etc. Those are valid bounds on the O(n) algorithm, just not the smallest.</text></comment>