Как определяется временная сложность операции получения элемента по индексу в списке?

Временная сложность операции получения элемента по индексу в списке зависит от типа списка:

• В массиве или списке с поддержкой индексирования (например, List<T> в C#) доступ по индексу — операция с временной сложностью O(1), так как элемент можно получить напрямую по адресу.
• В связном списке (односвязном или двусвязном) доступ по индексу — операция с временной сложностью O(n), так как для получения элемента нужно пройти по списку от начала (или конца) до нужной позиции.

В C# класс List<T> реализован на основе массива, поэтому доступ по индексу быстрый и имеет сложность O(1).