Milline on ajakulude keerukus operatsioonil, et lisada element ArrayList tüüpi massiivi lõppu?

ArrayList-tüüpi massiivi lõppu elementide lisamise ajakulude keskmine on O(1) — amortiseeritud konstantne aeg.

See toimub seetõttu, et ArrayList salvestab elemendid fikseeritud suurusega massiivis. Kui lisame elemendi ja massiivis on vaba koht, asetatakse element lihtsalt järgmisse lahtrisse.

Kui aga massiiv on täis, toimub laiendamise operatsioon — luuakse uus suurem massiiv ja kõik elemendid kopeeritakse sinna. See operatsioon võtab aega O(n), kus n on elementide arv.

Näide:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Kui massiivi maht saavutab limiidi, toimub laiendamine — O(n)

Seega, lisamise keskmine keerukus on — O(1), kuid halvimatel juhtudel — O(n).