Como é determinada a complexidade temporal da operação de obter um elemento por índice numa lista?

A complexidade temporal da operação de obter um elemento por índice numa lista depende do tipo de lista:

• Em um array ou lista com suporte de indexação (por exemplo, List<T> em C#), o acesso por índice é uma operação com complexidade temporal de O(1), pois o elemento pode ser obtido diretamente pelo endereço.

• Em uma lista ligada (simples ou duplamente ligada), o acesso por índice é uma operação com complexidade temporal de O(n), pois para obter o elemento é necessário percorrer a lista desde o início (ou o fim) até à posição desejada.

Em C#, a classe List<T> é implementada com base em um array, portanto, o acesso por índice é rápido e tem complexidade O(1).