Qual é a complexidade temporal da operação de inserção de um novo elemento numa matriz?

A inserção de um novo elemento numa matriz tem uma complexidade temporal de O(n) no pior caso, onde n é o número de elementos na matriz.

A razão é que a matriz tem um tamanho fixo, e para inserir um elemento no meio ou no início, é necessário deslocar todos os elementos subsequentes uma posição para a direita. Se a inserção ocorrer no final e houver espaço livre, a operação pode ser O(1).

Exemplo:

• Inserção no final com espaço disponível: O(1)
• Inserção no início ou no meio: O(n) devido ao deslocamento dos elementos

Em matrizes dinâmicas (por exemplo, ArrayList em Java), quando a matriz fica cheia, ocorre uma cópia para uma nova matriz de tamanho maior, o que também requer O(n) tempo.