2.11. Programming Exercises¶

1. Devise an experiment to verify that the list index operator is \(O(1)\)
2. Devise an experiment to verify that get item and set item are \(O(1)\) for dictionaries.
3. Devise an experiment that compares the performance of the del operator on lists and dictionaries.
4. Given a list of numbers in random order, write an algorithm that works in \(O(n\log(n))\) to find the kth smallest number in the list.
5. Can you improve the algorithm from the previous problem to be linear? Explain.