Dans quelles situations l'ajout d'un élément à la fin d'un ArrayList peut-il avoir une complexité temporelle de O(n) ?

L'ajout d'un élément à la fin d'un ArrayList a généralement une complexité temporelle amortie de O(1), mais dans certains cas, cela peut être O(n). Cela se produit lorsque le tableau interne qui stocke les éléments est plein et doit être agrandi.

Lors de l'ajout d'un nouvel élément :

• S'il y a de la place, l'élément est simplement ajouté — O(1).
• S'il n'y a pas de place, un nouveau tableau de taille plus grande est créé (généralement 1,5 à 2 fois plus grand), et tous les éléments existants sont copiés dans le nouveau tableau — cette opération est O(n).

Ainsi, l'ajout d'un élément peut avoir une complexité temporelle de O(n) précisément au moment de l'agrandissement du tableau interne.