Mi az időbeli komplexitása egy elem hozzáadásának a tömb elejéhez?

Egy elem hozzáadása a tömb elejére általában O(n) időkomplexitással jár, ahol n a tömbben lévő elemek száma.

Ez azért van, mert a kezdő pozícióba történő beszúráshoz minden meglévő elemet jobbra kell tolni, hogy helyet csináljunk az új elemnek. Dinamikus tömbökben (például Swift Array) ez a folyamat az elemek másolását vagy tolását igényli, ami az elemek számával arányos időt vesz igénybe.

Példa:

var array = [2, 3, 4]
array.insert(1, at: 0) // beszúrjuk az 1-et a kezdő pozícióba
print(array) // [1, 2, 3, 4]

Itt, amikor az 1-et beszúrjuk, minden elem egy pozícióval jobbra tolódik.