Hogyan határozhatjuk meg az időbeli költségeket egy ArrayList segítségével megvalósított tömb közepébe történő elem beszúrásakor?

Egy elem beszúrása egy ArrayList közepébe megköveteli az összes, beszúrás utáni elemet egy pozícióval jobbra tolni. Ez azt jelenti, hogy az időigény arányos ezeknek az elemeknek a számával.

Ha a lista méretét N-nek és a beszúrási pozíciót k-nek jelöljük, akkor a legrosszabb esetben (kezdeti beszúrás) szinte az összes N elemet el kell tolni, ami O(N) időkomplexitást eredményez. A végére történő beszúrás O(1), mivel nincs szükség tolásra.

Így a ArrayList segítségével történő tömb közepébe való beszúrás időbeli komplexitása körülbelül O(N - k), ahol k a beszúrás indexe.