title: List of Big-O for PHP functions
body: <p>After using PHP for a while now, I've noticed that not all built-in PHP functions are as fast as expected. Consider these two possible implementations of a function that finds if a number is prime using a cached array of primes.</p>
  
  <pre><code>//very slow for large $prime_array
  $prime_array = array( 2, 3, 5, 7, 11, 13, .... 104729, ... );
  $result_array = array();
  foreach( $prime_array =&gt; $number ) {
      $result_array[$number] = in_array( $number, $large_prime_array );
  }
  
  //speed is much less dependent on size of $prime_array, and runs much faster.
  $prime_array =&gt; array( 2 =&gt; NULL, 3 =&gt; NULL, 5 =&gt; NULL, 7 =&gt; NULL,
                         11 =&gt; NULL, 13 =&gt; NULL, .... 104729 =&gt; NULL, ... );
  foreach( $prime_array =&gt; $number ) {
      $result_array[$number] = array_key_exists( $number, $large_prime_array );
  }
  </code></pre>
  
  <p>This is because <code>in_array</code> is implemented with a linear search O(n) which will linearly slow down as <code>$prime_array</code> grows. Where the <code>array_key_exists</code> 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(n)).</p>
  
  <p>So far I've had to discover the big-O's via trial and error, and occasionally <a href="https://stackoverflow.com/questions/2350361/how-is-the-php-array-implemented-on-the-c-level">looking at the source code</a>. Now for the question...</p>
  
  <p><strong>Is there a list of the theoretical (or practical) big O times for all* the built-in PHP functions?</strong></p>
  
  <p>*or at least the interesting ones</p>
  
  <p>For example, I find it very hard to predict the big O of functions listed because the possible implementation depends on unknown core data structures of PHP: <code>array_merge</code>, <code>array_merge_recursive</code>, <code>array_reverse</code>, <code>array_intersect</code>, <code>array_combine</code>, <code>str_replace</code> (with array inputs), etc.</p>