Qual é a complexidade algorítmica de procurar um elemento por índice?

O(1).

Ao procurar um elemento por índice na maioria das estruturas de dados (por exemplo, em arrays ou ArrayList em Java), o endereço de memória da célula correspondente ao índice pode ser calculado diretamente. Isso requer tempo constante, independentemente do tamanho da estrutura de dados.