78

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

4 Answers 4

81

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: An Introduction to Python Lists.

4
  • 71
    So just to make it clear, list.pop(0) is O(n) and list.pop() is O(1). Commented Dec 21, 2016 at 19:59
  • 6
    And to get both operations in O(1), use collections.deque see here
    – galath
    Commented Aug 24, 2017 at 19:55
  • 5
    @galath: just to be clear, deque is not O(1) for removal of an arbitrary item (you didn't state that explicitly, I just wanted to ensure no misunderstanding), since it's a doubly linked list of blocks (ie, arrays), not individual elements. Hence it's still generally O(n). Removal of the first item in the deque is O(1), as the block has start and end indexes which can be manipulated without shifting element s around.
    – paxdiablo
    Commented Aug 17, 2020 at 6:31
  • @paxdiablo Sorry for not being more explicit. deque.pop does not accept an argument docs on deque, like the pop method from lists. It removes the rightmost element.
    – galath
    Commented Dec 4, 2020 at 17:44
47

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.

5
  • 6
    I agree with the answer given, but the explanation is imho wrong. You can remove any object from a list at O(1) time (essentially make prev pointer point to next, and remove this) The problem is that in order to FIND the object at that position, you need to traverse the list up to that point (takes O(N) time, no averaging needed.) Finally a special case note:, pop(0) will take O(1), not O(0).
    – ntg
    Commented Dec 11, 2017 at 10:07
  • 6
    @ntg the list is an array of pointers. to remove a pointer from the array in the middle, all the pointers following it have to be moved up in the array taking an amount of time proportional to the size of the list (which we denote as N), thus being O(N). To clarify the N in the Big-O notation is NOT the index of the element being returned, but a function bounding the running time of the algorithm with O(1) being constant time - i.e., it doesn't depend on the size of the list. O(N) means that the bounding function is some constant times the size of the list, f(n) = c*n + b.
    – tvanfosson
    Commented Dec 11, 2017 at 16:38
  • 1
    I stand corrected :) Indeed, the list implementation is an array of pointers. So your answer is correct. By pop(N) in your answer you mean pop(k),N where k is position of the element to remove, and the size of said array is N. Then k might range from 0 to N-1, thus per average N/2 operations to move the elements k+1,....,N-1 one position backwards.
    – ntg
    Commented Dec 12, 2017 at 9:12
  • 1
    @ntg pop(0) is O(N), not O(1)
    – Bill Yang
    Commented Jul 30, 2018 at 15:59
  • @BillYang Appologies, as said, I stand corrected. I was thinking of a classic linked list implementation (e.g. en.wikipedia.org/wiki/Linked_list) However, python's list seems to basically be an array of pointers...
    – ntg
    Commented Aug 14, 2018 at 13:37
10

The short answer is to look here: https://wiki.python.org/moin/TimeComplexity

With no arguments to pop, it is O(1)

With an argument to pop:

  • Average time Complexity O(k) (k represents the number passed in as an argument for pop)
  • Amortized worst case time complexity O(k)
  • Worst case time complexity O(n)

Average time complexity:

  • Any time you put in a value the time complexity of that operation is O(n - k).

  • For example, if you have a list of 9 items than removing from the end of the list is 9 operations and removing from the beginning of the list is 1 operations (deleting the 0th index and moving all the other elements to their current index - 1)

  • Since n - k for the middle element of a list is k operations the average can be shortened to O(k).

  • Another way to think about this is that imagine that each index was removed from your 9 item list once. That would be a total of 45 operations. (9+8+7+6+5+4+3+2+1 = 45)

  • 45 is equal to O(nk) and since the pop operation occurred O(n) times you divide nk by n to get O(k)

Amortized Worst Case Time Complexity

  • Imagine you have a list of 9 items again. Imagine you're removing every item of the list and the worst case occurs and you remove the first item of the list each time.

  • Since the list shrinks by 1 each time the number of total operations decreases each time from 9 through 1.

  • 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45. 45 equals O(nk). Since you made 9 operations and 9 is O(n) to calculate the amortized worst case scenario you do O(nk) / O(n) which equals O(k)

  • Stating it's O(n) for the average and amortized worst case time complexity is also sort of correct. Notice that O(k) is approximately O(1/2n) and dropping the constant equals O(n)

Worst Case Time Complexity

  • Unlike with amortized worst case time complexity you don't factor in the state of the data structure and just think about the worst case for any individual operation.
  • In that instance, the worst case is you have to remove the 1st item from the list which is O(n) time.

Here's what I wrote to think this through in case it helps:

7

It should be O(1) with L.pop(-1), and O(n) with L.pop(0)

See the following example:

from timeit import timeit
if __name__ == "__main__":
    L = range(100000)
    print timeit("L.pop(0)",  setup="from __main__ import L", number=10000)
    L = range(100000)
    print timeit("L.pop(-1)", setup="from __main__ import L", number=10000)

>>> 0.291752411828
>>> 0.00161794329896
2
  • why this happen? what's the deference of 'L.pop(0)' and L.pop(-1)
    – Amir133
    Commented Mar 31, 2021 at 9:19
  • @Amir133 0 and -1 are the indices of the element to remove from list L. 0 is the first element, and - 1 means the last element. Python allows negative indices to count from the end of the list, with -1 as the last, -2 as the second last etc Commented Nov 18, 2023 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.