2.11. Exercícios de Programação¶

1. Faça um experimento para verificar que o acesso a um elemento através de seu índice em uma lista é $O(1)$.

2. Faça um experimento para verificar que o acesso e atribuição a um item de um dicionário é $O(1)$.

3. Faça um experimento para comparar a performance do operador del em listas e dicionários.

4. Dada uma lista de números em ordem aleatória, escreva um algoritmo que funcione em $O(n\log(n))$ para achar o k-ésimo menor número da lista.

5. Você pode melhorar o algoritmo do problema anterior para que ele seja linear? Explique.