V ktorých situáciách môže pridanie prvku na koniec ArrayList mať časovú zložitosť O(n)?

Pridanie prvku na koniec ArrayList zvyčajne má amortizovanú časovú zložitosť O(1), ale v niektorých prípadoch môže byť O(n). To sa deje, keď je vnútorný poľ, ktorý uchováva prvky, plný a je potrebné ho rozšíriť.

Pri pridávaní nového prvku:

• Ak je miesto, prvok sa jednoducho pridá — O(1).
• Ak miesto nie je, vytvorí sa nový poľ väčšej veľkosti (zvyčajne 1,5-2 krát väčší), a všetky existujúce prvky sa skopírujú do nového poľa — tá operácia je O(n).

Týmto spôsobom môže pridanie prvku mať časovú zložitosť O(n) práve v momente rozšírenia vnútorného poľa.