2.12. Programming Exercises¶

1. Devise an experiment to verify that the vector index operator is \(O(1)\)
2. Devise an experiment to verify that find and insert are \(O(1)\) for hash tables.
3. Devise an experiment that compares the performance of the erase() operator on vectors and hash tables.
4. Given an array of numbers in random order, write an algorithm that works in \(O(n\log(n))\) to find the kth smallest number in the array.
5. Can you improve the algorithm from the previous problem to be linear? Explain.