Mekkora az időbeli komplexitás az elem kivétele index alapján egy tömbben?

Az elemhez való hozzáférés időbeli komplexitása index alapján egy tömbben O(1), azaz állandó.

Ez abból adódik, hogy a tömbök a memóriában egymás után, szekvenciális blokkokként vannak tárolva, és az elemhez való hozzáférés közvetlenül a cím kiszámításával történik: a tömb alapcíme plusz egy eltolás, amely az elem méretétől és az indextől függ.

Például Swift vagy Objective-C nyelven a tömbök úgy vannak megvalósítva, hogy az index szerinti hozzáférés azonnali, anélkül, hogy végig kellene nézni az elemeket.