Всегда ли pop() удаляет последний элемент? Как меняется сложность при pop(i)?

У Python list вызов pop() удаляет последний элемент; pop(i) удаляет элемент по индексу и сдвигает последующие. Для начала списка это O(n), для конца — амортизированно O(1).

Стоимость сдвига составляет O(n − i − 1) для неотрицательного допустимого индекса; отрицательный индекс сначала приводится к позиции. Удаление последнего элемента обычно не двигает ссылки, но редкое изменение размера выделенного массива может потребовать перераспределения памяти. Пустой список или неверный индекс вызывают IndexError. Это ответ именно про list: у dict pop(key) принимает ключ, у set pop() удаляет произвольный элемент. Для частого удаления с начала очереди подходит deque.popleft().