Your algorithm universe is the algorithms of Subject 1. Rad the problem very carefully and pick your problem size even more carefully.

You are given a sequence X of m comparable keys. You need to devise a DECISION algorithm that detects the presence of duplicate keys. Two keys X[ i ] and X[ j ] i not eq to j are duplicates if X[ i ]==X[ j ]. Your algorithm answers with a YES if there is a (one or more) pair of duplicate keys such as X[ i ],X[ j ] and NO otherwise. It is not an optimization algorithm that finds the i and j and the X[ i ]==X[ j ], i.e. locations and value of a pair of duplicates.

(a) What is the running time of a time efficient algorithm for detecting duplicates ?

(b) What is the running time of a time efficient algorithm for detecting duplicates that uses also constant extra space beyond the space for X ?