A pair is a simple struct with two data members, one of type T and one...

 

Transcribed Image Text:

A pair is a simple struct with two data members, one of type T and one of type T2. A set and a map are organized as binary search trees; an unordered set and an unordered map are organized as hash tables that never allow the load factor to exceed some constant, and visiting every item in hash table of N items is O(N) Suppose has C courses each of which has on average S students enrolled. For this problem, courses Suppose 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 students 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&#39;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, which is O (log S).) in these problems, we&#39; re just looking for the answer you don&#39;t need to write the reason. a. vector<>>>, where each pair in the outer vector represents a course and all the students in that class, with those students being sorted in order. The pairs are in no particular order in the outer vector. What is the big-O complexity of determining whether a particular student s is enrolled in course c? b. map>, where the students in each list are in no particular order. What is the big-O? c. map>? What is the big-O complexity of determining whether a particular students is enrolled in course c? d. unordered map>. What is the big-O complexity to determine whether a particular complexity to determine whether a particular students is enrolled in course c? enrolled in course c? student s is enrolled in course c? A pair is a simple struct with two data members, one of type T and one of type T2. A set and a map are organized as binary search trees; an unordered set and an unordered map are organized as hash tables that never allow the load factor to exceed some constant, and visiting every item in hash table of N items is O(N) Suppose has C courses each of which has on average S students enrolled. For this problem, courses Suppose 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 students 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&#39;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, which is O (log S).) in these problems, we&#39; re just looking for the answer you don&#39;t need to write the reason. a. vector<>>>, where each pair in the outer vector represents a course and all the students in that class, with those students being sorted in order. The pairs are in no particular order in the outer vector. What is the big-O complexity of determining whether a particular student s is enrolled in course c? b. map>, where the students in each list are in no particular order. What is the big-O? c. map>? What is the big-O complexity of determining whether a particular students is enrolled in course c? d. unordered map>. What is the big-O complexity to determine whether a particular complexity to determine whether a particular students is enrolled in course c? enrolled in course c? student s is enrolled in course c?