Python's list implementation uses a dynamically resized C array under the hood, removing elements usually requires you to move elements following after up to prevent gaps.

list.pop() with no arguments removes the last element. Accessing that element can be done in constant time. There are no elements following so nothing needs to be shifted.

list.pop(0) removes the first element. All remaining elements have to be shifted up one step, so that takes O(n) linear time.

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.

O(k) when k = n-1 is really the same as O(n) where time complexity is concerned.

Yes. list.pop(0) is O(n), and deque.popleft() is O(1).

Nice observation! You are correct in that the performance of pop(0) is significantly slower than pop() for large lists (above 10,000 elements). See timeit results below. I believe @Kenneth Love (https://teamtreehouse.com/kennethlove) chose to pop from the front of the list as a straight-forward logical approach without trying to optimize for performance. Since the order of monsters in the list is arbitrary, popping from the back or the front isn't a requirement and either approach would work functionally. Using timeit in the python REPL: ```python import timeit stmt1 = "while foo: it = foo.pop();" stmt2 = "while foo: it = foo.pop(0);" Run on 1000 element list setup = "foo = list(range(1000))" timeit.timeit(stmt1, setup) 0.051728010177612305 timeit.timeit(stmt2, setup) 0.05761384963989258 Run on 10,000 element list setup = "foo = list(range(10000))" timeit.timeit(stmt1, setup) 0.05236983299255371 timeit.timeit(stmt2, setup) 0.06780695915222168 Run on 100,000 element list setup = "foo = list(range(100000))" timeit.timeit(stmt1, setup) 0.0552210807800293 timeit.timeit(stmt2, setup) 1.3619050979614258 Run on 1,000,000 element list setup = "foo = list(range(1000000))" timeit.timeit(stmt1, setup) 0.10635495185852051 timeit.timeit(stmt2, setup) 226.78901600837708 ```

On modern CPython implementations, pop takes amortized constant-ish time (I'll explain further). On Python 2, it's usually the same, but performance can degrade heavily in certain cases.

A Python set is based on a hash table, and pop has to find an occupied entry in the table to remove and return. If it searched from the start of the table every time, this would take time proportional to the number of empty leading entries, and it would get slower with every pop.

To avoid this, the standard CPython implementation tries to remember the position of the last popped entry, to speed up sequences of pops. CPython 3.5+ has a dedicated finger member in the set memory layout to store this position, but earlier versions abuse the hash field of the first hash table entry to store this index.

On any Python version, removing all elements from a set with a sequence of pop operations will take time proportional to the size of the underlying hash table, which is usually within a small constant factor of the original number of elements (unless you'd already removed a bunch of elements). Mixing insertions and pop can interfere heavily with this on Python 2 if inserted elements land in hash table index 0, trashing the search finger. This is much less of an issue on Python 3.