Beware Big O Notation in higher level languages

(written by lawrence krubner, however indented passages are often quotes). You can contact lawrence at:, or follow me on Twitter.

This essay has a nice bit of details about a general point that needs to be made:

Here we get the result that will be counterintuitive to many. No matter how large n gets, the Array List still performs better overall. In order for performance to get worse, the ratio of inserts to iterations has to change, not just the length of the collection. Note that isn’t an actual failure of Big O analysis, it is merely a common human failure in our application of it. If you actually “did the math”, Big O would tell you that the two data structures here will grow at the same speed when there is a constant ratio of inserts to iterations.

Where the break even point occurs will depend on many factors, though a good rule of thumb suggested by Chandler Carruth at Google is that Array Lists will outperform Linked Lists until you are inserting about an order of magnitude more often than you are iterating

I’d make a broader point: when dealing with high level languages, you can not be sure what kind of data structure you are dealing with. PHP has something called an “array” but it is nothing like a low level array, so don’t try to analyze it with Big O Notation. The name “array” is just marketing, its really a complex object that has little to do with an array, except that it tries to imitate familiar aspects of an array. Generally, you need to use the specialized functions that PHP makes available, to do complex work with PHP’s “array”. The same goes for Ruby.

Post external references

  1. 1