20

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

Example

$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
Reese Moore
  • 11,524
  • 3
  • 24
  • 32
Lu4
  • 14,873
  • 15
  • 79
  • 132
  • 3
    Does this answer your question? [Is PHP's count() function O(1) or O(n) for arrays?](https://stackoverflow.com/questions/5835241/is-phps-count-function-o1-or-on-for-arrays) – ggorlen Oct 10 '20 at 13:31

2 Answers2

25

$ 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)

tstenner
  • 10,080
  • 10
  • 57
  • 92
20

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

Puppy
  • 144,682
  • 38
  • 256
  • 465