Question

Write the function has duplicate() which takes as input a vector v and outputs true if there is a re-

peated element in v and false if there is no repeated elements. Below is the algorithm which you

should implement.

default output is 0

for elt1 in v:

for elt2 later in v than elt1:

if elt1==elt2, make output 1, break, end

end

end

Checking if elt1==elt2 counts as one step. Setting the output value also counts as one step.

(a) How many steps does it take for the input of v=[1, 3, 3, 7, 9]? List each step in order.

(b) What’s the most number of steps it could take for a length 5 input?

(c) What’s the most number of steps it could take for a length n input?

Answer 1