Next Section - 3. Basic Data Structures
2.11. Programming Exercises
- Devise an experiment to verify that the list index operator is
- Devise an experiment to verify that get item and set item are
\(O(1)\) for dictionaries.
- Devise an experiment that compares the performance of the
operator on lists and dictionaries.
- 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.
- Can you improve the algorithm from the previous problem to be linear? Explain.