<story><title>WTF Is Big O Notation?</title><url>https://rob.conery.io/2019/03/25/wtf-is-big-o-notation</url></story><parent_chain><item><author>gpm</author><text>This seems like a good time to bring up one of my pet peeves about big O notation.&lt;p&gt;Every theoretical model I&amp;#x27;ve ever seen says that indexing into n bits of memory takes O(1) time. That&amp;#x27;s obviously impossible:&lt;p&gt;- The pointer you need to read is log(n) bits.&lt;p&gt;- The physical memory is at best O(n^(1&amp;#x2F;3)) distance away from the CPU, and thus takes that much time to get back to you. In reality it&amp;#x27;s probably O(n^(1&amp;#x2F;2)) because we build on flat planes (once you start talking about petabytes of data anyways).&lt;p&gt;Maybe this doesn&amp;#x27;t matter in practice, because the constants associated with these are small enough (but are they, how many memory&amp;#x2F;disk bound applications are there? How much extra performance could we squeeze out by using 16&amp;#x2F;32 bit pointers for small arrays?). It certainly doesn&amp;#x27;t matter in theory where things work like we say they do regardless of the physical reality. But it annoys me that it&amp;#x27;s so obviously wrong.</text></item></parent_chain><comment><author>anon946</author><text>Well, it&amp;#x27;s &amp;quot;wrong&amp;quot;, but there&amp;#x27;s the saying that all models are wrong, but some are useful. If time complexity analysis had to include physical distance, then it would perhaps be less wrong, but also much less useful.&lt;p&gt;That said, &amp;quot;time complexity&amp;quot; is a bit of a misnomer anyway. It&amp;#x27;s often implied, but underneath, there is a specific operation. For example, when we say that merge sort is O(N lg N), we mean in number of comparison operations.</text></comment>
<story><title>WTF Is Big O Notation?</title><url>https://rob.conery.io/2019/03/25/wtf-is-big-o-notation</url></story><parent_chain><item><author>gpm</author><text>This seems like a good time to bring up one of my pet peeves about big O notation.&lt;p&gt;Every theoretical model I&amp;#x27;ve ever seen says that indexing into n bits of memory takes O(1) time. That&amp;#x27;s obviously impossible:&lt;p&gt;- The pointer you need to read is log(n) bits.&lt;p&gt;- The physical memory is at best O(n^(1&amp;#x2F;3)) distance away from the CPU, and thus takes that much time to get back to you. In reality it&amp;#x27;s probably O(n^(1&amp;#x2F;2)) because we build on flat planes (once you start talking about petabytes of data anyways).&lt;p&gt;Maybe this doesn&amp;#x27;t matter in practice, because the constants associated with these are small enough (but are they, how many memory&amp;#x2F;disk bound applications are there? How much extra performance could we squeeze out by using 16&amp;#x2F;32 bit pointers for small arrays?). It certainly doesn&amp;#x27;t matter in theory where things work like we say they do regardless of the physical reality. But it annoys me that it&amp;#x27;s so obviously wrong.</text></item></parent_chain><comment><author>mwfunk</author><text>Part of it is that there&amp;#x27;s very casual, conversational usages of Big O vs. much more formal usages when trying to actually quantify performance.&lt;p&gt;Conversational Big O tends to include a lot of spherical cows (&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Spherical_cow&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Spherical_cow&lt;/a&gt;), because when Big O comes up in conversation, people are more likely to be talking in generalities about high level designs. More detail could be counterproductive in that context.&lt;p&gt;When someone is actually trying to quantify and predict performance of an algorithm, then the other extreme becomes desirable- the more detailed and specific the function, the better.</text></comment>