In welchen Situationen kann das Hinzufügen eines Elements am Ende einer ArrayList eine Zeitkomplexität von O(n) haben?

Das Hinzufügen eines Elements am Ende einer ArrayList hat in der Regel eine amortisierte Laufzeitkomplexität von O(1), kann aber in einigen Fällen O(n) sein. Dies geschieht, wenn das interne Array, das die Elemente speichert, voll ist und erweitert werden muss.

Beim Hinzufügen eines neuen Elements:

• Wenn Platz vorhanden ist, wird das Element einfach hinzugefügt — O(1).
• Wenn kein Platz mehr ist, wird ein neues Array größerer Größe erstellt (in der Regel 1,5- bis 2-mal größer), und alle bestehenden Elemente werden in das neue Array kopiert — diese Operation ist O(n).

Daher kann das Hinzufügen eines Elements genau beim Erweitern des internen Arrays eine Laufzeitkomplexität von O(n) haben.