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)