Extreme Python

Logo

Extremely good python content :)

About

Articles

Python list operations and their runtime complexity

by Alan

In this article we’re going to go over common list mutation and query operations and their runtime complexity. Python lists are implemented as dynamic arrays, so the time complexity of list operations is equivalent to the time complexity of dynamic arrays.

Just as a refresher on the big O of a dynamic array data structure, here’s a table from wikipedia:

Operation Runtime Complexity
Indexing O(1)
Insert/delete at beginning O(N)
Insert/delete at end O(1) amortized
Insert/delete in middle O(1)

List operation performance

Given a list of integers stored in the variable numbers, here’s are tables of the run time complexity of query and mutation actions. Query actions do not change the existing list, but mutations do.

Note: assume that all index values used in the examples are in range.

Queries

Action Syntax Runtime Complexity
Does x exist in list? x in numbers O(n)
Get element at index 5 numbers[5] O(n)
Get subarray between index 2 and 7 (including 7) numbers[2:8] O(k)
Get length len(numbers) O(k)

Mutations

Action Syntax Runtime Complexity
Add 3 to the end of the list numbers.append(3) O(1)
Insert 3 to the beginning of the list numbers.insert(0, 3) O(n)
Insert 3 to the middle of the list numbers.insert(4, 3) O(n)
Pop the last element on the list numbers.pop() O(1)
Pop an element from the middle of the list numbers.pop(4) O(k)
Pop an element from the beginning of the list numbers.pop(0) O(n)
Add a list of elements to the end of the list numbers.extend(other_numbers) O(k)

FAQs

Why are inserts to the end of a list O(1)? Doesn’t python have to allocate a new list and copy all the existing lists over?

Good question! Python actually over-allocates in proportion tho the list size, which means that not all appends result in full list copies. Taking into account the over allocation, python claims to have a O(1) append runtime.

tags: