В кои ситуации добавянето на елемент в края на ArrayList може да има времева сложност O(n)?

Добавянето на елемент в края на ArrayList обикновено има амортизирана времева сложност O(1), но в някои случаи може да бъде O(n). Това се случва, когато вътрешният масив, който съхранява елементите, е пълен и трябва да бъде разширен.

При добавяне на нов елемент:

• Ако има място, елементът просто се добавя — O(1).
• Ако няма място, се създава нов масив с по-голям размер (обикновено 1,5-2 пъти по-голям), и всички съществуващи елементи се копират в новия масив — тази операция е O(n).

Следователно, добавянето на елемент може да има времева сложност O(n) точно в момента на разширяване на вътрешния масив.