Since it doesn't seem like anyone has done this before I thought it'd be good idea to have it for reference somewhere. I've gone though and either via benchmark or code-skimming to characterize the `array_*`

functions. I've tried to put the more interesting Big-O near the top. This list is not complete.

Note: All the Big-O where calculated assuming a hash lookup is O(1) even though it's really O(n). The coefficient of the n is so low, the ram overhead of storing a large enough array would hurt you before the characteristics of lookup Big-O would start taking effect. For example the difference between a call to `array_key_exists`

at N=1 and N=1,000,000 is ~50% time increase.

**Interesting Points**:

`isset`

/`array_key_exists`

is much faster than `in_array`

and `array_search`

`+`

(union) is a bit faster than `array_merge`

(and looks nicer). But it does work differently so keep that in mind.
`shuffle`

is on the same Big-O tier as `array_rand`

`array_pop`

/`array_push`

is faster than `array_shift`

/`array_unshift`

due to re-index penalty

**Lookups**:

`array_key_exists`

O(n) but really close to O(1) - this is because of linear polling in collisions, but because the chance of collisions is very small, the coefficient is also very small. I find you treat hash lookups as O(1) to give a more realistic big-O. For example the different between N=1000 and N=100000 is only about 50% slow down.

`isset( $array[$index] )`

O(n) but really close to O(1) - it uses the same lookup as array_key_exists. Since it's language construct, will cache the lookup if the key is hardcoded, resulting in speed up in cases where the same key is used repeatedly.

`in_array`

O(n) - this is because it does a linear search though the array until it finds the value.

`array_search`

O(n) - it uses the same core function as in_array but returns value.

**Queue functions**:

`array_push`

O(∑ var_i, for all i)

`array_pop`

O(1)

`array_shift`

O(n) - it has to reindex all the keys

`array_unshift`

O(n + ∑ var_i, for all i) - it has to reindex all the keys

**Array Intersection, Union, Subtraction**:

`array_intersect_key`

if intersection 100% do O(Max(param_i_size)*∑param_i_count, for all i), if intersection 0% intersect O(∑param_i_size, for all i)

`array_intersect`

if intersection 100% do O(n^2*∑param_i_count, for all i), if intersection 0% intersect O(n^2)

`array_intersect_assoc`

if intersection 100% do O(Max(param_i_size)*∑param_i_count, for all i), if intersection 0% intersect O(∑param_i_size, for all i)

`array_diff`

O(π param_i_size, for all i) - That's product of all the param_sizes

`array_diff_key`

O(∑ param_i_size, for i != 1) - this is because we don't need to iterate over the first array.

`array_merge`

O( ∑ array_i, i != 1 ) - doesn't need to iterate over the first array

`+`

(union) O(n), where n is size of the 2nd array (ie array_first + array_second) - less overhead than array_merge since it doesn't have to renumber

`array_replace`

O( ∑ array_i, for all i )

**Random**:

`shuffle`

O(n)

`array_rand`

O(n) - Requires a linear poll.

**Obvious Big-O**:

`array_fill`

O(n)

`array_fill_keys`

O(n)

`range`

O(n)

`array_splice`

O(offset + length)

`array_slice`

O(offset + length) or O(n) if length = NULL

`array_keys`

O(n)

`array_values`

O(n)

`array_reverse`

O(n)

`array_pad`

O(pad_size)

`array_flip`

O(n)

`array_sum`

O(n)

`array_product`

O(n)

`array_reduce`

O(n)

`array_filter`

O(n)

`array_map`

O(n)

`array_chunk`

O(n)

`array_combine`

O(n)

I'd like to thank Eureqa for making it easy to find the Big-O of the functions. It's an amazing *free* program that can find the best fitting function for arbitrary data.

EDIT:

For those who doubt that PHP array lookups are `O(N)`

, I've written a benchmark to test that (they are still effectively `O(1)`

for most realistic values).

```
$tests = 1000000;
$max = 5000001;
for( $i = 1; $i <= $max; $i += 10000 ) {
//create lookup array
$array = array_fill( 0, $i, NULL );
//build test indexes
$test_indexes = array();
for( $j = 0; $j < $tests; $j++ ) {
$test_indexes[] = rand( 0, $i-1 );
}
//benchmark array lookups
$start = microtime( TRUE );
foreach( $test_indexes as $test_index ) {
$value = $array[ $test_index ];
unset( $value );
}
$stop = microtime( TRUE );
unset( $array, $test_indexes, $test_index );
printf( "%d,%1.15f\n", $i, $stop - $start ); //time per 1mil lookups
unset( $stop, $start );
}
```

27Totally off topic but, 1 is not prime. – Jason Punyon – 2010-03-18T23:13:57.157

Good call Jason Punyon – Kendall Hopkins – 2010-03-18T23:16:11.293

22

Arrays in PHP are hashtables. That should tell you everything you need to know. Searching for a key in a hashtable is O(1). Searching for a value is O(n) -- which you can't beat on an unsorted set. Most of the functions you're curious about are probably O(n). Of course, if you really want to know, you can read the source: http://cvs.php.net/viewvc.cgi/php-src/ext/standard/array.c?revision=1.308.2.21.2.37.2.57&view=markup

– Frank Farmer – 2010-03-18T23:19:40.07311For the record, the fastest implementation of what you're trying to do would be to (instead of using NULL for your values) use

`true`

and then test for presence using`isset($large_prime_array[$number])`

. If I remember correctly, it's in the order of being hundreds of times faster than the`in_array`

function. – mattbasta – 2010-03-19T01:50:58.2731mattbasta; if what you say is true then i just learned the coolest thing i've learned all week. – echo – 2010-03-19T04:46:58.730

@mattbasta wouldn't it still has the same big-O, but just a smaller coefficient? – Kendall Hopkins – 2010-03-19T05:47:38.187

@Kendall Not really sure, but I've used it and it's CRAZY fast. – mattbasta – 2010-03-19T19:59:48.547

@mattbasta According to my tests the only reason that isset is faster is because it's a language construct and there is a bit of over head for array_key_exists. This overhead

– Kendall Hopkins – 2010-03-20T16:44:55.757according to my test http://pastebin.com/E9WtuzPbis only ~50% (difference between 0.0000006 and 0.0000004). I believe the reason isset can be orders of magnitude faster is because it can cache lookups when the key is hardcoded, because it's a language construct. I think i'll still stick with array_key_exists because it doesn't have the NULL gotcha.3The Big O notation is not about speed. It’s about limiting behavior. – Gumbo – 2010-03-20T17:22:48.880

2@Kendall I'm not comparing to

`array_key_exists`

, I'm comparing to`in_array`

.`in_array`

iterates each item in the array and compares the value to the needle which you pass to it. If you flip the values to the key (and just replace each of the values with a dummy value like`true`

, using`isset`

is many many times faster. This is because the keys of an array are indexed by PHP (like a hashtable). Consequently, searching an array in this manner can have a significant improvement in speed. – mattbasta – 2010-03-20T17:53:42.450Interesting! So a quick conversion to use the 2nd, faster form, is to use $prime_array = array_fill_keys( $prime_array, null ) . This turns keys into values and now we can use isset() instead of in_array(). From http://stackoverflow.com/questions/10641865/php-array-turning-array-values-into-keys

– Jorge Orpinel – 2014-10-21T21:14:25.583$array_of_number is not defined ?? – Rizwan Shamsher Kaim Khani – 2016-05-12T21:03:34.867