COT 3100 sec. #7094X
Quiz #3 - Algorithms & Complexity

You have ten minutes.Name: _________________________
Problem 1 (Algorithms). (10 points):

Write a pseudo-code description of a simple algorithm that will determine whether there are any duplicates in an unordered input list of numbers L = (a1, a2, ... , an). In other words, given any L (and its length n), the algorithm should determine the truth value of the proposition
i j (i j ai = aj) in a universe of discourse consisting of the natural numbers from 1 to n. You may want to use constructs such as for loops, if statements, and assignment statements (the := operator). To return the final answer, your algorithm may use statements such as "return TRUE" and "return FALSE".


















Problem 2 (Complexity). (10 points):

For the algorithm you described in problem 1, let Tmax(n) denote its time complexity, defined as the maximum total number of steps (individual comparisons, assignments, etc.) that your algorithm might perform given an input list of length n. What is the order of growth of Tmax(n), as a function of n? Use big-Theta () notation, and state the answer as simply as possible.



Briefly state how you arrived at your answer.