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

A complexidade temporal para obter um elemento por índice num array é O(1), ou seja, constante.

Isto ocorre porque os arrays na memória são armazenados como um bloco sequencial, e o acesso a um elemento por índice é feito diretamente através do cálculo do endereço: endereço base do array mais um deslocamento, que depende do tamanho do elemento e do índice.

Por exemplo, em Swift ou Objective-C, os arrays são implementados de forma que o acesso por índice seja instantâneo, sem percorrer os elementos.