Como determinar o custo em tempo da operação de inserção de um novo elemento numa matriz?

A inserção de um novo elemento em um array depende do tipo de array e do método de inserção:

• Para arrays estáticos (tamanho fixo): inserir no final é O(1), se houver espaço livre. Inserir no meio ou no início é O(n), pois é necessário deslocar os elementos.
• Para arrays dinâmicos (por exemplo, ArrayList em Java ou NSMutableArray em iOS):
  • Inserção no final geralmente é amortizada O(1), mas ao encher o array, ocorre uma realocação de memória e cópia — O(n).
  • Inserção no meio ou no início é O(n), devido ao deslocamento dos elementos.

Portanto, o custo em tempo depende da posição de inserção e da implementação do array. Normalmente, inserir no final de um array dinâmico é amortizado rápido, enquanto as outras inserções requerem deslocar elementos e têm complexidade linear.