What's the time complexity of adding an element to an array?

Question

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?

Community · Accepted Answer · 2020-06-20 09:12:55Z

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.

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Nov 2, 2015 at 17:33

q.Then

2,7411 gold badge24 silver badges31 bronze badges

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

5 Comments

Mark Amery Over a year ago

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.

q.Then Over a year ago

My answer is pretty much the same as Mark Baker, if you so wish, this has been semi covered before pretty elaborately: stackoverflow.com/questions/2473989/…, 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. php.net/manual/en/language.types.array.php

Mark Amery Over a year ago

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 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 Baker Over a year ago

PHP7 does change the rules for a whole host of things, but technically isn't publicly released for another 10 days yet

Akhmed Over a year ago

O(n+cm), where n is the number of items in array and m is the number of items being added

Mark Baker · Accepted Answer · 2015-11-02 17:30:49Z

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

answered Nov 2, 2015 at 17:30

Mark Baker

213k34 gold badges354 silver badges390 bronze badges

2 Comments

Mark Amery Over a year ago

This seems plausible, but do you have a source for it, or a detailed explanation based upon how the underlying data structure works?

Mark Baker Over a year ago

You can take my word on it, or read 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

Collectives™ on Stack Overflow

What's the time complexity of adding an element to an array?

2 Answers 2

Constant time O(1)

Linear time O(n)

5 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Constant time O(1)

Linear time O(n)

5 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related