CODEWITHSUNDEEP
phparrayscomplexity-theory
kristian
kristian

Reputation: 350

Time/Space complexity of PHP Array

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

Upvotes: 19

Views: 12245

Answers (3)

Mike Lewis
Mike Lewis

Reputation: 64147

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

Upvotes: 19

Vladislav Rastrusny
Vladislav Rastrusny

Reputation: 29985

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

Upvotes: 1

KingCrunch
KingCrunch

Reputation: 131891

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?

Upvotes: 6

Related Questions