Kaip nustatoma laiko sudėtingumas operacijai gauti elementą pagal indeksą sąraše?

Laiko sudėtingumas operacijai gauti elementą pagal indeksą sąraše priklauso nuo sąrašo tipo:

• Masive arba sąraše su indeksavimo palaikymu (pavyzdžiui, List<T> C#), prieiga pagal indeksą yra operacija su O(1) laiko sudėtingumu, nes elementą galima gauti tiesiogiai per adresą.

• Susietame sąraše (viengubo arba dvigubo ryšio), prieiga pagal indeksą yra operacija su O(n) laiko sudėtingumu, nes norint pasiekti elementą, reikia pereiti per sąrašą nuo pradžios (arba pabaigos) iki norimos pozicijos.

C# klasė List<T> yra įgyvendinta remiantis masyvu, todėl prieiga pagal indeksą yra greita ir turi sudėtingumą O(1).