AFAIK, Python «спецификация» не навязывает конкретные структуры данных для реализации списков, словарей или наборов, поэтому на этот вопрос нельзя ответить «официально».Если вас интересует только CPython (эталонная реализация), мы можем добавить некоторые неофициальные сложности.Возможно, вы захотите переформулировать свой вопрос, чтобы указать конкретную реализацию Python.
В любом случае упомянутые вами сложности могут быть неправильными.Предполагая реализацию массива с динамическим изменением размера, добавление элемента амортизируется O(1): чаще всего вы просто копируете новое значение, а в худшем случае вам необходимо перераспределить, копируя все элементы n плюс новый,Далее, вставка имеет точно такой же сценарий наихудшего случая, поэтому она имеет ту же верхнюю границу сложности, но в лучшем случае она перемещает только k элементов, где k - количество элементов мимо * 1008.* позиция, в которую вы вставляете.