Mekkora az időbeli komplexitása van egy új elem beszúrásának egy tömbbe?

Egy új elem beszúrása egy tömbbe a legrosszabb esetben O(n) időkomplexitással jár, ahol n a tömbben lévő elemek száma.

Az oka, hogy a tömb fix méretű, és a közepébe vagy a kezdetére történő beszúráshoz minden további elemet egy pozícióval jobbra kell tolni. Ha a beszúrás a végén történik, és van szabad hely, az művelet lehet O(1).

Példa:

• A végére történő beszúrás szabad hely esetén: O(1)
• A kezdetére vagy közepére történő beszúrás: O(n) az elemek eltolása miatt

Dinamikus tömbökben (pl. Java ArrayList) a tömb megtelésekor másolás történik egy nagyobb méretű új tömbbe, ami szintén O(n) időt igényel.