The Myth of RAM (2014)
I think there&#x27;s some good info in this article covered by various degrees of misinformation. For some reason, the article starts off with this totally wrong definition of big-O, and proceeds to make conclusions with this wrong definition. Let me provide the accurate definition:<p>The statement &quot;f is O(g)&quot; means there exists some input, call it t, such that for every x &gt;= t, it only takes some constant multiplier M (i.e., constant in x) to <i>always</i> have g absolutely no smaller than f. In notation:<p>|f(x)| &lt;= M * |g(x)|, where x is at least t.<p>This bit about &quot;x is at least t&quot; is very important and notifies us that this is &quot;asymptotic behavior&quot;.<p>It does not make a difference how wacky or weird f is compared to g below t. It can contain all these crazy memory hierarchy artifacts, it could contain a short burst of exponential slowdown, it could contain anything.<p>Furthermore, according to the above definition, big-O has nothing to do with any tangible quantity whatsoever. It&#x27;s a method for comparing functions. The functions may represent whatever is of tangible or intangible interest: memory, time, money, instructions, ...<p>Big-O analysis usually posits that the details below t aren&#x27;t the details that matter. (Of course, there are situations where they do, but in such you would not use big-O.) If you want to have some analysis that is global, you don&#x27;t need asymptotic analysis (though it might help as a start). You can just talk about functions that are strictly greater than or less than your function of interest everywhere. But these analyses are difficult because a much higher level of understanding of your function of interest is required.