2

PHP's arrays are complex beasts; they allow rapid lookups like an ordinary hash table, but their key-value pairs are also ordered. How does the time cost of inserting an element into this structure change as the number of existing elements grows?

Does the time complexity depend upon exactly how I'm inserting the element into the array? For instance, do each of these operations:

array_unshift($array, $value);
array_push($array, $value);
array['some_new_key'] = $value;

have the same time complexity, or different time complexities?

Mark Amery
  • 143,130
  • 81
  • 406
  • 459

2 Answers2

5

Constant time O(1)

array_push is constant time (queue function for a hash-table like structure), an interesting note however is that performance-wise:

array_push();
$array[] = $val;

The latter method is faster than array_push due to no cost to pay for overhead function call.

Linear time O(n)

Definitely array_push and related queue functions are much faster than array_unshift. Yes they all preform the same functionality but in different ways to accomplish this. As you already noted, PHP's arrays are extremely powerful and provide robust functionality. This comes at a cost, as PHP's arrays have ordered keys, and you need to pay an extra cost to re-index all these keys, so O(n). array_unshift would then take the linear time of the array + the constant time to append the values to the head of the array, so something similar to O(n + cn'), where c is the constant time to add an element to the array and n' is the number of items being added.

Community
  • 1
  • 1
q.Then
  • 2,743
  • 1
  • 21
  • 31
  • Same question as to Mark Baker - what's your source? This is what I'd expect, but I'd prefer either an authoritative reference or an explanation based upon how the underlying data structure to just taking your word. – Mark Amery Nov 02 '15 at 17:42
  • 1
    My answer is pretty much the same as Mark Baker, if you so wish, this has been semi covered before pretty elaborately: http://stackoverflow.com/questions/2473989/list-of-big-o-for-php-functions, or you can read the php source code. Also, it states in the PHP site that arrays are implemented as hash tables, which should already infer enough about their performance. http://php.net/manual/en/language.types.array.php – q.Then Nov 02 '15 at 17:45
  • I don't think all this follows trivially from a shallow knowledge of the data structure; for example, it looks like `array_shift` could plausibly be `O(1)` if the data structure's ordering were implemented by storing a linked list of keys. As for your first link, it hasn't been updated since [arrays were reimplemented](https://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html) for PHP 7. This may all seem very obvious to you, but I'm going to read around some more before upvoting or accepting anything. – Mark Amery Nov 02 '15 at 17:55
  • PHP7 does change the rules for a whole host of things, but technically isn't publicly released for another 10 days yet – Mark Baker Nov 02 '15 at 18:00
  • O(n+cm), where n is the number of items in array and m is the number of items being added – Akhmed Jun 15 '20 at 12:28
4
array_push($array, $value);

and

array['some_new_key'] = $value;

are both O(1)

array_unshift($array, $value);

is O(n) because (changing the "head") it has to shuffle the entire array to handle the ordering

Mark Baker
  • 209,507
  • 32
  • 346
  • 385
  • This seems plausible, but do you have a source for it, or a detailed explanation based upon how the underlying data structure works? – Mark Amery Nov 02 '15 at 17:35
  • You can take my word on it, or read http://www.phpinternalsbook.com/hashtables/basic_structure.html, or you can check with the php source code.... oddly, I actually gave a talk which included this at PHPBarcelona over the weekend – Mark Baker Nov 02 '15 at 17:38