Какова сложность удаления элемента из списка, множества и словаря?

У списка удаление по индексу обычно O(n) из-за сдвига, кроме конца — O(1) амортизированно. У dict и set удаление по ключу в среднем O(1), но при плохих коллизиях может быть O(n).

list.remove(value) дополнительно ищет значение, поэтому даже удаление последнего по значению не становится O(1). У pop() без индекса поиск не нужен. Для словаря и множества оценки предполагают недорогие hash и сравнение ключей; пользовательские реализации могут сделать их существенно дороже. Также различайте удаление одной записи и очистку всей структуры: освобождение ссылок на n элементов требует обхода, а их финализаторы могут добавить работу.