Comment la complexité temporelle est-elle déterminée lors de l'ajout d'un élément à ArrayList?

La complexité temporelle d'ajouter un élément à ArrayList est généralement amortie à O(1). Cela est dû au fait que :

• Si le tableau interne de ArrayList a de l'espace libre, le nouvel élément est simplement écrit à la prochaine position — l'opération prend un temps constant O(1).
• Si le tableau interne est plein, il est étendu : un nouveau tableau de taille plus grande est créé, et tous les éléments y sont copiés. Cette opération prend O(n), où n est la taille actuelle de la liste.

Cependant, l'extension ne se produit pas à chaque ajout, mais périodiquement, donc la complexité moyenne (amortie) de l'ajout reste O(1).

Exemple :

ArrayList<Integer> list = new ArrayList<>();
list.add(10); // Amortie O(1)