Answer The Following Multiple Choice Questions And Choose the Correct Answer (A-D).

Question 1:

Put the following time complexity descriptions in the correct order - fastest on the left, slowest on the right.

(N^2 means N squared. If you're not sure, try plotting them on a chart.)

Question 1 options:

A.	O(1) < O(log N) < O(N) < O(N log N) < O(N^2)
B.	O(1) < O(log N) < O(N log N) < O(N) < O(N^2)
C.	O(1) < O(N) < O(log N) < O(N log N) < O(N^2)
D.	O(1) < O(N) < O(log N) < O(N^2) < O(N log N)

Question 2:

This function checks whether a vector contains any 7s.

bool HasSevens(vector& items) { for (int i = 0; i < items.size(); i++) { if (items[i] == 7) { return true; } } return false; }

Which of the following would best describe its time complexity, where N is the length of the vector?

Question 2 options:

A.	O(1)
B.	O(log N)
C.	O(N)
D.	O(N^2)

Question 3:

This function checks whether a string contains any character more than once. It would return false for "pear" or "quince", and true for "banana" or "apple".

The string class behaves like an array; indexing with [] is O(1).

bool HasDuplicates(const string& word) { // For each character in the word... for (int i = 0; i < word.size(); i++) { // Does the character match an earlier character? for (int j = 0; j < i; j++) { if (word[i] == word[j]) { // Yes -- so there's at least one duplicate return true; } } } // We didn't find any duplicates return false; }

Which of the following would best describe its time complexity, where N is the length of the string?

Question 3 options:

A.	O(1)
B.	O(log N)
C.	O(N)
D.	O(N^2)

Question 4:

This function inserts an item into an ordered (sorted) list only if it isn't already present. It uses the LinearSearch and InsertOrdered algorithms we saw in the lecture, which are both O(N).

void InsertOrderedIfNew(int item, list& items) { // If the item is already present, do nothing if (LinearSearch(item, items)) { return; } // Insert the item into the ordered collection InsertOrdered(items, item); }

The overall time complexity of this function is O(N), where N is the length of items. If you changed it to use BinarySearch rather than LinearSearch, which of the following would best describe its overall time complexity (bearing in mind the simplification rules we saw in the lecture)?

Question 4 options:

A.	O(1)
B.	O(log N)
C.	O(N)
D.	O(N^2)

Question 5:

We saw that singly linked lists use more memory than vectors to store the same data.

How would you describe the memory usage of the two data structures using big-O notation (bearing in mind the simplification rules we saw in the lecture), where N is the number of items stored?

Question 5 options:

A.	Lists use O(N) memory, vectors use O(N^2) memory
B.	Lists use O(N) memory, vectors use O(2N) memory
C.	Lists and vectors both use O(N) memory
D	Lists use O(1) memory, vectors use O(N) memory