Menu
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?
918
The time complexity of the python list pop() function is constant O(1). It does not matter how many elements are in the list, removing an element from a list takes the same time and it does not depend on the number of elements to be popped. The reason for this is that in cPython lists are implemented with arrays.
Python list. pop(0) is extremely slow for a large list.
Python list pop() is an inbuilt function in Python that removes and returns the last value from the List or the given index value.
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
130
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() for an arbitrary element to be O(N) and require on average N/2 operations since you would need to move any elements beyond the element you are removing one position up in the array of pointers.
43
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
