Qual é a complexidade temporal de obter um elemento pelo seu número de ordem numa lista de array?

A complexidade temporal para obter um elemento pelo seu número de ordem num array (ArrayList ou array normal) é O(1), ou seja, a operação é realizada em tempo constante.

Isto deve-se ao fato de que os arrays armazenam os elementos numa região contínua de memória, e o acesso a um elemento por índice é feito diretamente através do cálculo do endereço.

Exemplo em Java:

int[] arr = {10, 20, 30, 40};
int elemento = arr[2]; // Obtemos o terceiro elemento (30) em O(1)

No entanto, se se tratar de listas ligadas (LinkedList), o acesso por índice terá uma complexidade temporal de O(n), pois é necessário percorrer os elementos desde o início até ao desejado.