What is the time complexity of popping elements from list in Python?

Question

I wonder what is the time complexity of pop method of list objects in Python (in CPython particulary). Also does the value of N for list.pop(N) affects the complexity?

Answer 1

I found this link that might provide some insight. Based on this, pop() for the last element ought to be O(1) since you only need to return the element referred to by the last element in the array and update the index of the last element. I would expect pop(N) to be O(N) and require on average N/2 operations since you would need to move any elements beyond the Nth one, one position up in the array of pointers.

FWIW, I don't have any idea if the referenced link is accurate, though it does seem to be a reasonable implementation.

Answer 2

Yes, it is O(1) to pop the last element of a Python list, and O(N) to pop an arbitrary element (since the whole rest of the list has to be shifted).

Here's a great article on how Python lists are stored and manipulated: http://effbot.org/zone/python-list.htm