Complexidade amortizada: o array dinâmico

Resposta esperada

A maioria dos pushes é O(1) (só escreve na próxima posição). De vez em quando o array enche e precisa realocar: aloca o dobro e copia os N elementos — essa operação é O(N). Mas isso acontece cada vez mais raro (a cada 1, 2, 4, 8, ... elementos), e o custo total de todas as cópias ao inserir N elementos é N + N/2 + N/4 + ... < 2N, ou seja O(N) para N inserções → O(1) por inserção na média. 'Amortizado' é justamente essa média sobre a sequência de operações, não o pior caso de uma operação isolada. Diferente de 'caso médio', que é sobre distribuição de entrada — amortizado é garantido sobre qualquer sequência. Importa saber a distinção quando latência de pico (p99) importa: um push individual ainda pode ser O(N) e causar um espasmo, mesmo sendo O(1) amortizado.