Description
The description provided for this problem:
Compare two back ends for a dictionary, such as a binary tree and a hash table. For example, in the C++ standard library, std::multimap can be used to easily store a dictionary of key-value pairs in a balanced binary tree, while std::unordered_multimap can be used to store values in a hash table. Other structures such as a sorted array could also be used as possible dictionary back ends..
In theory, a hash table should be faster for insertions and deletions, but how much faster? Compare the two for insertion of n = 10, n = 100, n = 1000, …, n = as high as you need to go for at least one of the data structures to take more than 3 seconds to run.
Generate a graph comparing the performance. You may use other data structures and implementations in another language if you prefer not to use C++, but make sure you know what you are using.
Upload your write-up (see the assignment description for what should go into the write-up) as a pdf along with any associated supporting files (e.g., source code, etc).
