Time/Space complexity of PHP Array

Question

Is there a way or a resource for finding the time and space complexity of the Array implementation in PHP other than calculating it by hand?

An array in PHP is actually an ordered map. A map is a type that associates values to keys. This type is optimized for several different uses; it can be treated as an array, list (vector), hash table (an implementation of a map), dictionary, collection, stack, queue, and probably more. As array values can be other arrays, trees and multidimensional arrays are also possible. - php.net

From what I can tell it would seem that it has the general complexity of a map

In the average case is O(1) but the worst case is O(n) with malicious handling: murilo.wordpress.com/2013/10/16/… — Murilo Vasconcelos
– Murilo Vasconcelos, Commented Oct 19, 2013 at 4:29

Mikaël Mayer · Accepted Answer · 2017-02-27 09:11:09Z

21

Because it acts like a hash table, you will have O(1) time when accessing an element by a key.

If you are looping through the array, naturally you will have O(n) time.

If you have time, you can actually check out PHP's implementation of array here

edited Feb 27, 2017 at 9:11

Mikaël Mayer

10.8k7 gold badges67 silver badges106 bronze badges

answered Apr 12, 2011 at 20:24

Mike Lewis

64.3k20 gold badges144 silver badges111 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

KingCrunch · Accepted Answer · 2011-04-12 20:31:16Z

7

Accessing and iterating is describe by @Mike-Lewis so far

Setting a value: O(1)
Append: O(1) (Its the same as setting a value to the key "length")
Prepend: O(n) (Its a guess, but should fit, because it should rewrite the existing keys)
Unset: O(1)

Anything missed?

answered Apr 12, 2011 at 20:31

KingCrunch

133k22 gold badges158 silver badges174 bronze badges

1 Comment

Max Over a year ago

- Insert: O(n) (It's guess, because the existing values which come after the new one have to be rewritten)

Vladislav Rastrusny · Accepted Answer · 2011-04-12 20:33:22Z

1

In addition to what @Mike Lewis said, I would add, that one array element in PHP occupies minimum of 52 bytes (proof)

answered Apr 12, 2011 at 20:33

Vladislav Rastrusny

30.2k23 gold badges100 silver badges158 bronze badges

3 Comments

sanmai Over a year ago

Just for the record, as of 2020 for PHP 7.3 this amount is about 2.5 times less. More about this.

Olle Härstedt Over a year ago

Anyone knows the memory performance of SplFixedArray compared to array?

George Tiganila Over a year ago

How about php8, has this reduced in memory usage?

Collectives™ on Stack Overflow

Time/Space complexity of PHP Array

3 Answers 3

Comments

1 Comment

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related