Hoe wordt de tijdcomplexiteit van de bewerking om een element op index in een lijst te verkrijgen, bepaald?

De tijdscomplexiteit van de operatie om een element op index te verkrijgen in een lijst hangt af van het type lijst:

• In een array of lijst met ondersteuning voor indexering (bijvoorbeeld List<T> in C#), is de toegang op index een operatie met een tijdscomplexiteit van O(1), omdat het element direct via het adres kan worden verkregen.

• In een gelinkte lijst (enkel- of dubbel gelinkt), is de toegang op index een operatie met een tijdscomplexiteit van O(n), omdat je door de lijst moet lopen vanaf het begin (of het einde) tot de gewenste positie.

In C# is de klasse List<T> geïmplementeerd op basis van een array, dus de toegang op index is snel en heeft een complexiteit van O(1).