Qual é a complexidade temporal da operação de busca de todos os elementos por índice?

O(1) em média para listas graças ao acesso direto por índice. No caso de dicionários (dict), a busca por chave também é O(1) em média.