title: When does Big-O notation fail?
body: <p>What are some examples where Big-O notation[1] fails in practice?</p>
  
  <p>That is to say: when will the Big-O running time of algorithms predict algorithm A to be faster than algorithm B, yet in practice algorithm B is faster when you run it?</p>
  
  <p>Slightly broader: when do theoretical predictions about algorithm performance mismatch observed running times? A non-Big-O prediction might be based on the average/expected number of rotations in a search tree, or the number of comparisons in a sorting algorithm, expressed as a factor times the number of elements.</p>
  
  <p><strong>Clarification</strong>:</p>
  
  <p>Despite what some of the answers say, the Big-O notation <strong>is</strong> meant to predict algorithm performance.  That said, it's a <strong>flawed</strong> tool: it only speaks about asymptotic performance, and it blurs out the constant factors.  It does this for a reason: it's meant to predict algorithmic performance independent of which computer you execute the algorithm on.</p>
  
  <p><em>What I want to know is this</em>: when do the flaws of this tool show themselves?  I've found Big-O notation to be reasonably useful, but far from perfect.  What are the pitfalls, the edge cases, the gotchas?</p>
  
  <p>An example of what I'm looking for: running Dijkstra's shortest path algorithm with a Fibonacci heap instead of a binary heap, you get O(m + n log n) time versus O((m+n) log n), for n vertices and m edges.  You'd expect a speed increase from the Fibonacci heap sooner or later, yet said speed increase never materialized in my experiments.</p>
  
  <p>(Experimental evidence, without proof, suggests that binary heaps operating on uniformly random edge weights spend O(1) time rather than O(log n) time; that's one big gotcha for the experiments.  Another one that's a bitch to count is the expected number of calls to DecreaseKey).</p>
  
  <p>[1] Really it isn't the <em>notation</em> that fails, but the <em>concepts</em> the notation stands for, and the theoretical approach to predicting algorithm performance.  &lt;/anti-pedantry&gt;</p>
  
  <p><strong>On the accepted answer</strong>:</p>
  
  <p>I've accepted an answer to highlight the kind of answers I was hoping for.  Many different answers which are just as good exist :)  What I like about the answer is that it suggests a general rule for when Big-O notation "fails" (when cache misses dominate execution time) which might also increase understanding (in some sense I'm not sure how to best express ATM).</p>