Mekkora az időbeli komplexitása annak az műveletnek, amikor egy elemet beszúrunk a dinamikus ArrayList elejére?

Dinamikus tömbbe (például Java-ban ArrayList) elem beszúrása a kezdethez időkomplexitással O(n), ahol n a tömbben lévő elemek száma.

Ez azért van, mert a kezdethez történő beszúráskor minden meglévő elemet egy pozícióval jobbra kell mozgatni, hogy helyet csináljunk az új elemnek. Az elemek másolási folyamata lineáris időt vesz igénybe.

Példa:

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

// Kezdethez való beszúrás
list.add(0, 0); // minden elemet jobbra mozgat

Ezért a végéhez való beszúrás általában gyorsabb (amortizált O(1)), míg a kezdethez való O(n).