Skip to main content\(
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 2.12 Programming Exercises
-
Devise an experiment to verify that the vector index operator is
\(O(1)\text{.}\)
-
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.
