Como avaliar a complexidade temporal da operação de remover um elemento de um array?

A complexidade temporal de remover um elemento de um array depende do tipo de array e do método de remoção:

• Num array padrão (por exemplo, Array em Swift), remover um elemento por índice requer deslocar todos os elementos seguintes para a esquerda para preencher o "buraco". Isso leva a uma complexidade de O(n), onde n é o número de elementos após o elemento removido.

• Se o último elemento for removido, a operação geralmente é feita em O(1), pois não é necessário deslocamento.

• No caso de arrays dinâmicos (por exemplo, ArrayList em Java ou NSMutableArray em Objective-C), a situação é semelhante: remover do meio requer deslocar os elementos.

Exemplo:

var array = [1, 2, 3, 4, 5]
array.remove(at: 2) // remove o elemento no índice 2 (o número 3)
// Após a remoção, os elementos 4 e 5 deslocam-se uma posição para a esquerda

Portanto, em geral, remover um elemento de um array é uma operação com complexidade de tempo O(n).