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

O(1).

При поиске элемента по индексу в большинстве структур данных (например, в массивах или ArrayList в Java), адрес памяти ячейки, соответствующей индексу, может быть вычислен напрямую. Это требует константного времени, независимо от размера структуры данных.