Qual é a complexidade temporal de adicionar um elemento à lista Python no final, início e meio?

Em Python, as listas são implementadas como arrays dinâmicos, portanto, a complexidade temporal das operações depende da posição de inserção:

• Adicionar ao final (list.append(element)) — O(1) amortizado, pois geralmente há espaço, mas às vezes ocorre uma redistribuição de memória.
• Adicionar ao início (list.insert(0, element)) — O(n), porque todos os elementos são deslocados para a direita.
• Adicionar no meio (list.insert(index, element)) — também O(n), pois os elementos após o índice são deslocados.

Portanto, para uma adição eficiente ao início ou ao meio, é melhor usar outras estruturas de dados, como collections.deque.