Kuidas määratakse ajakulude keerukus, lisades elementi ArrayListi?

ArrayList elementide lisamise ajakulud on tavaliselt amortiseeritud tasemel O(1). See tuleneb sellest, et:

• Kui ArrayListi sisemine massiiv on vaba ruumi, kirjutatakse uus element lihtsalt järgmisele positsioonile — operatsioon võtab konstantselt aega O(1).
• Kui sisemine massiiv on täis, toimub selle laienemine: luuakse suurem massiiv ja kõik elemendid kopeeritakse sinna. See operatsioon võtab O(n) aega, kus n on nimekirja praegune suurus.

Kuid laienemine ei toimu iga lisamise korral, vaid perioodiliselt, seega jääb lisamise keskmine (amortiseeritud) keerukus O(1)-le.

Näide:

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