Question

A pair is a simple struct with two data members, one of type T1 and one of type T2. A set and a map are organized as binary search trees; anunordered_set and an unordered_map are organized as hash tables that never allow the load factor to exceed some constant, and a loop that visits every item in a hash table of N items is O(N).

Suppose UCLA has C courses each of which has on average S students enrolled. For this problem, courses are represented by strings (e.g. "CS 32"), and students by their int UIDs. We will consider a variety of data structures, and for each determine the big-O time complexity of the appropriate way to use that data structure to determine whether a particular student s is enrolled in course c. For example, if the data structure were vector>>, where each pair in the outer vector represents a course and all the students in that course, with those students being sorted in order, then if the pairs are in no particular order in the outer vector, the answer would be O(C + log S). (The reason is that we'd have to do a linear search through the outer vector to find the course, which is O(C), and then after that do a binary search of the S students in the sorted vector for that course, which is O(log S).) In these problems, we're just looking for the answer; you don't need to write the reason.

e. unordered_map>. What is the big-O complexity to determine whether a particular student s is enrolled in course c?

f. Suppose we have the data structure map> and we wish for a particular course c to write the id numbers of all the students in that course in sorted order. What is the big-O complexity?

g. Suppose we have the data structure unordered_map> and we wish for a particular course c to write the id numbers of all the students in that course in sorted order (perhaps using an additional container to help with that). What is the big-O complexity?

h. Suppose we have the data structure unordered_map> and we wish for a particular student s to write all the courses that student is enrolled in, in no particular order. What is the big-O complexity?

Answer 1

(e) unordered_map<string, unordered_set<int>>

The outer unordered_map is a hash table, so to search the course c it would take constant time O(1). and once we have the course and its unordered_set , which is again a hash table so to serach the student s it would take constant time O(1).So total time is O(1), constant.

(f) map<string, set<int>>

The outer map is a binary search tree, so to search the course c it would take logC time and once we have the course and its set, which is a binary tree, to list the ids in sorted order we need to do an inorder traversal of the tree that would take O(S) time.So total time is O(logC+S)

(g) unordered_map<string, unordered_set<int>>

The outer unordered_map is a hash table, so to search the course c it would take constant time O(1). and once we have the course and its onordered_set , which is another hash table, to list the ids in sorted order we need to loop through all elements in the hash table which takes O(S) time and sort them using any sorting algorithms or else construct another container set<int> that takes O(SlogS) time. So total time is O(SlogS).

(h) unordered_map<string, set<int>>

The outer unordered_map is a hash table, so we loop through each course in it and do search for the student s in its set<int>, which is a binary search tree, if found we print the course else not. The search takes logS time for each course, so total time is O(ClogS).