Cost of list functions in Python

Question

Based on this older thread, it looks like the cost of list functions in Python is:

• Random access: O(1)
• Insertion/deletion to front: O(n)
• Insertion/deletion to back: O(1)

Can anyone confirm whether this is still true in Python 2.6/3.x?

Answer 1

Take a look here. It's a PEP for a different kind of list. The version specified is 2.6/3.0.

Append (insertion to back) is O(1), while insertion (everywhere else) is O(n). So yes, it looks like this is still true.

Operation...Complexity
Copy........O(n) 
Append......O(1)
Insert......O(n) 
Get Item....O(1)
Set Item....O(1)
Del Item....O(n) 
Iteration...O(n)
Get Slice...O(k)
Del Slice...O(n)
Set Slice...O(n+k)
Extend......O(k) 
Sort........O(n log n)
Multiply....O(nk)

Answer 2

Python 3 is mostly an evolutionary change, no big changes in the datastructures and their complexities.

The canonical source for Python collections is TimeComplexity on the Wiki.