PHP_FUNCTION(count) вызывает php_count_recursive(), который в свою очередь вызывает zend_hash_num_elements() для нерекурсивного массива, который реализован следующим образом:
ZEND_API int zend_hash_num_elements(const HashTable *ht)
{
IS_CONSISTENT(ht);
return ht->nNumOfElements;
}
Итак, вы можете видеть, это O(1) для $mode = COUNT_NORMAL.