CODEWITHSUNDEEP
phpbig-o
Christoph Diegelmann
Christoph Diegelmann

Reputation: 2034

Big-O of PHP arrays

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 !

Upvotes: 1

Views: 966

Answers (1)

laurie
laurie

Reputation: 708

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.

Upvotes: 3

Related Questions