Qual é a complexidade temporal da operação de inserir um elemento no início de uma ArrayList dinâmica?

A inserção de um elemento no início de um array dinâmico (por exemplo, ArrayList em Java) tem uma complexidade de tempo de O(n), onde n é o número de elementos no array.

Isto deve-se ao fato de que, ao inserir no início, todos os elementos existentes precisam ser deslocados uma posição para a direita para abrir espaço para o novo elemento. O processo de copiar os elementos leva tempo linear.

Exemplo:

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

// Inserção no início
list.add(0, 0); // desloca todos os elementos para a direita

Assim, inserir no final costuma ser mais rápido (amortizado O(1)), enquanto no início é O(n).