Is PHP's count() function O(1) or O(n) for arrays?

Does count() really count the all the elements of a PHP array, or is this value cached somewhere and just gets retrieved?

Well, we can look at the source:

/ext/standard/array.c

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)
{
	IS_CONSISTENT(ht);

	return ht->nNumOfElements;
}

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

In PHP 5+ the length is stored in the array so the counting is not done each time.

EDIT: You also might find this analysis interesting: PHP Count Performance. Although the length of the array is maintained by the array, it still seems as though it is faster to hold on to it if you are going to call count() many times.

PHP stores the size of an array internally, but you're still making a function call when which is slower than not making one, so you'll want to store the result in a variable if you're doing something like using it in a loop:

For example,

$cnt = count($array);
for ($i =0; $i < $cnt; $i++) {
   foo($array[$i]);
}

Additionally, you can't always be sure count is being called on an array. If it's called on an object that implements Countable for example, the count method of that object will be called.