List of Big-O for PHP functions?

Posted by Kendall Hopkins on Stack Overflow See other posts from Stack Overflow or by Kendall Hopkins
Published on 2010-03-18T23:12:32Z Indexed on 2010/03/19 6:31 UTC
Read the original article Hit count: 192

Filed under:
|
|
|
|

After using PHP for a while now, I've noticed that not all PHP built in functions as fast as expected. Consider the below two possible implementations of a function that finds if a number is prime using a cached array of primes.

//very slow for large $prime_array
$prime_array = array( 2, 3, 5, 7, 11, 13, .... 104729, ... );
$result_array = array();
foreach( $array_of_number => $number ) {
    $result_array[$number] = in_array( $number, $large_prime_array );
}

//still decent performance for large $prime_array
$prime_array => array( 2 => NULL, 3 => NULL, 5 => NULL, 7 => NULL,
                       11 => NULL, 13 => NULL, .... 104729 => NULL, ... );
foreach( $array_of_number => $number ) {
    $result_array[$number] = array_key_exists( $number, $large_prime_array );
}

This is because in_array is implemented with a linear search O(n) which will linearly slow down as $prime_array grows. Where the array_key_exists function is implemented with a hash lookup O(1) which will not slow down unless the hash table gets extremely populated (in which case it's only O(logn)).

So far I've had to discover the big-O's via trial and error, and occasionally looking at the source code. Now for the question...

I was wondering if there was a list of the theoretical (or practical) big O times for all* the PHP built in functions.

*or at least the interesting ones

For example find it very hard to predict what the big O of functions listed because the possible implementation depends on unknown core data structures of PHP: array_merge, array_merge_recursive, array_reverse, array_intersect, array_combine, str_replace (with array inputs), etc.

© Stack Overflow or respective owner

Related posts about php

Related posts about big-o