1

EDIT: This is a duplicate question, but I had trouble understanding the wiki page despite reading the accepted answer there. I just added an answer to that question, which also covers the time complexity for the average case and amortized worst case scenario.

This Python wiki says that when you pass in an argument to a list's pop method that its worst case time complexity is O(k) with k referring to the number passed in for k or the number of elements in k.

However, if say I pop the 3rd index of a list of 11 elements wouldn't everything after the 3rd element of the list have to be re-adjusted making the average time complexity O(n-k) And since you could remove the first element of a list wouldn't the worst case time complexity be O(n)?

list1 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']
list2 = list1
print(list1[3]) # d
list1.pop(3)
print(list1) # ['a', 'b', 'c', 'e', 'f', 'g', 'h', 'i', 'j', 'k']
print(list1[3]) # e
print(id(list1) == id(list2)) # True (They're still the same item in memory)

Is there some unique way Python implements lists under the hood that I'm not understanding? Or is the wiki wrong?

Gwater17
  • 2,018
  • 2
  • 19
  • 38
  • 1
    In the average and worst cases, O(k) is the same as O(n) as they differ at most by a constant factor. – DYZ Sep 10 '17 at 00:48
  • @DYZ What do you mean by that? – Gwater17 Sep 10 '17 at 01:17
  • 1
    Removing items towards the front of the list *will* be slower than removing items at the end, you're correct -- however, the *average* is still in O(*k*). If you assume that removing the (*k*-1)th element takes 0 shift operations, the (*k*-2)th element takes 1 shift operations, ..., then the first element takes *k*-1 operations to remove. The average over all of these is still in O(*k*). Note that first line of the section: "The Average Case assumes parameters generated uniformly at random." – jedwards Sep 10 '17 at 01:23
  • 1
    In brief: There is no difference between O(k) and O(n). – DYZ Sep 10 '17 at 03:24

0 Answers0