2.11. Programming Exercises¶
Devise an experiment to verify that the
list indexoperator is \(O(1)\).
Devise an experiment to verify that
set itemare \(O(1)\) for dictionaries.
Devise an experiment that compares the performance of the
deloperator 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.