What is the Big-O time complexity of the count() function for arrays?


$x = array(1,2,3);
echo count($x); // how many operation does it takes to count the elements 
                // of the array? is it 3, or is it 1

3 Answers

tstenner On Best Solutions

$ time php -r '$a=range(1,1000000); $b=0; for($i=0;$i<10;$i++) $b=count($a);'
real    0m0.458s
$ time php -r '$a=range(1,1000000); $a=array(1); $b=0; for($i=0;$i<10;$i++) $b=count($a);'
real    0m0.457s
Seems pretty O(1) to me.

Tested PHP version: PHP 5.3.3-1ubuntu9.1 with Suhosin-Patch (cli) (built: Oct 15 2010 14:00:18)

Puppy On

Arrays have O(1) size- that is, their size is stored somewhere. The language updates the count on insertion/deletion.

QuidamAzerty On

If you want to known the source of count, another thread has answered to it: Is PHP's count() function O(1) or O(n) for arrays?

Here's the answer:

PHP_FUNCTION(count) calls php_count_recursive(), which in turn calls zend_hash_num_elements() for non-recursive array, which is implemented this way:

ZEND_API int zend_hash_num_elements(const HashTable *ht)

    return ht->nNumOfElements;

So you can see, it's O(1) for $mode = COUNT_NORMAL.