Можете ли вы помочь мне найти наихудшую сложность для большого кода для этого кода?

Question

У меня была викторина в классе, и я не очень хорошо с ней справился. Я пытаюсь выяснить, может ли кто-нибудь объяснить мне, что я здесь сделал неправильно - наш профессор перегружен рабочим временем, так как мы перешли в онлайн из-за COVID-19, поэтому я решил опубликовать здесь, так как еще не слышал ответ.

def functionC(L):
    for i in range(len(L)):
        if L[i] == i:
            v = L.pop(i)
            L.insert(i, 2*v)
    return

Я предоставил следующий ответ:

Вышеприведенной функцией является O (n), потому что for-l oop увеличивается с размером L. Функции pop и insert имеют постоянное время.

слово время вычеркнуто, но другого объяснения тому, почему я получил 6/10 за этот вопрос, нет. Что я ошибся в этом и почему?

Вот изображение вопроса и мой ответ, чтобы доказать, что тест уже оценен и передан обратно.

Answer 1

Время извлечения и вставки в середину массива составляет O(N) время с точки зрения длины массива. Таким образом, общая сложность времени составляет O(N^2). Вы получаете только O(1) pop и insert при работе с концом массива, так как остальные элементы не должны быть смещены, но это O(N) в другом месте.

Answer 2

Если вы посмотрите на этот python вики сложность по времени , вы увидите сложность Вспомогательный средний и insert перечислены как O (n) , что в свою очередь приводит к приведенному выше коду O (n ^ 2)