What's the time complexity of getting an element in an array in PHP?

Question

I've little idea of how arrays are implemented in PHP, and know that for most OOP languages the complexity is one of constant time, O(1), for an array of a predefined type. So what's the deal in PHP with it's dynamic typing, extending arrays, etc.?

Answer 1

Looking at array.c in the PHP source code reveals that they're implemented as hash tables, which means typically O(1) (it's actually O(N) if you're very strict but can be as bad as O(log N)) for looking up an element.

If in doubt, you can always measure though. Create an array of 10, 100, 1000, 10000, 100000, 1000000 etc elements and measure the performance, extrapolate the data to a function and you will have the average performance characteristics.