#### Before you keep reading...

Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.

#### Before you keep reading...

Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.

# 2.12. Programming Exercises

Devise an experiment to verify that the vector index operator is
\(O(1)\)

Devise an experiment to verify that find and insert are
\(O(1)\) for hash tables.

Devise an experiment that compares the performance of the `erase()`

operator on vectors and hash tables.

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.

Can you improve the algorithm from the previous problem to be linear? Explain.

You have attempted

of

activities on this page