Qual é a complexidade temporal de obter um elemento de um array por índice?

A complexidade temporal de obter um elemento de um array por índice é O(1), ou seja, constante. Isto deve-se ao fato de que os arrays na memória são armazenados como um bloco contíguo, e o acesso a um elemento por índice é feito diretamente através do cálculo do endereço: endereço base do array mais o índice multiplicado pelo tamanho do elemento.

Exemplo em Go:

arr := []int{10, 20, 30, 40}
value := arr[2] // Obtém o elemento com índice 2, value == 30

Este acesso não depende do tamanho do array, portanto é muito eficiente.