Big-O of PHP arrays

Question

After reading the answers to List of Big-O for PHP functions I got a little curious.

The Answer of Kendall Hopkins states that php lookups are O(n) for large arrays and constant time (means O(1) ?!) for small. He posted an image containing a graph which shows the time a constant amount of lookups (1 million) take depending on the size of the array. It starts almost vertically and then flattens.

From what I learned constant time means that the time taken is not a function of the elements in the array which means a horizontal graph not a vertical. I think his graph looks more like O(log n) which would fit the comments stating PHP implements recursive hash tables.

I did my own testing (using his script) and the graph turned out pretty much the same (PHP 5.3.23).

As this is a top rated answer I'm a little bit scared. Can you tell me if I'm getting this whole O(x) thing wrong? If so please help me.

Anyway: @Kendall Hopkins Thanks for your great answer !

laurie · Accepted Answer · 2013-08-16 10:09:20Z

3

You're correct in saying that Kendall Hopkins's statement is confusing / incorrect (though the rest of his post is a pretty awesome benchmarking reference).

Saying that an algorithm is O(1) for small inputs is a rather nonsensical statement. Saying an algorithm is O(1) means that the running time will always be less than a constant. Therefore, if we constrict our input space to a finite set (i.e. 'small' inputs) then any algorithm will be O(1), because we can just take the longest running time from that set as our constant.

What he means, is that, for an initial range of inputs, increasing the size of the array will make little difference to the running-time of the array.

If you want to learn more about big-O notation, then the [http://en.wikipedia.org/wiki/Analysis_of_algorithms wikipedia page] is a great jumping off point.

answered Aug 16, 2013 at 10:09

laurie

7086 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Big-O of PHP arrays

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related