3.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.

You have attempted 1 of 1 activities on this page