Qual é a complexidade temporal da operação de adicionar um elemento a um array dinâmico?

A adição de um elemento a um array dinâmico geralmente tem uma complexidade de tempo amortizada de O(1).

Explicação:

• Se houver espaço livre no array, o elemento é adicionado em tempo constante.
• Se não houver espaço, o array aloca um novo bloco de memória maior (normalmente o dobro), copia os elementos antigos e adiciona o novo.

Embora a operação de expansão leve O(n), ela não ocorre frequentemente, portanto a complexidade média (amortizada) de adicionar permanece O(1).

Exemplo em Go usando slices:

var arr []int
arr = append(arr, 10) // adiciona um elemento

append expandirá automaticamente o slice se necessário.