Comment déterminer le coût temporel lors de l'insertion d'un élément au milieu d'un tableau implémenté via ArrayList?

L'insertion d'un élément au milieu d'un ArrayList nécessite de décaler tous les éléments situés après la position d'insertion d'une position vers la droite. Cela signifie que le temps requis est proportionnel au nombre de ces éléments.

Si l'on note la taille de la liste par N et la position d'insertion par k, alors dans le pire cas (insertion au début), il faut décaler presque tous les N éléments, ce qui donne une complexité temporelle de O(N). L'insertion à la fin est O(1), car aucun décalage n'est nécessaire.

Ainsi, l'insertion au milieu d'un tableau via ArrayList a une complexité temporelle de l'ordre de O(N - k), où k est l'indice d'insertion.