Question

Exercise 3 (2 pts). Consider the following decision problem: Given a list of integers, deter- mine whether all elements of the list are distinct. Is this problem in P? Yes, no, unknown? Justify your answer (if your answer is "yes", briefly describe a polynomial-time algorith)

Answer 1

Answer:

The algorithm with polynomial time complexity is as follows:

It is in P (quickly Polynomial time solvable)

• We are having a set of numbers. Say there are n numbers

• We can choose the smallest of all that numbers. Say this will be of linear complexity because we need to make 1 pass comparing each number to find out the minimum of all the numbers.

• Now we can start dividing all the numbers by (2,3,4....up to the minimum number).If Any number divides all of them, then they will not be relatively prime otherwise The set of numbers can be considered as not relatively prime.

• Considering checking whether a number divides a number or not can be taken as of Constant time complexity. Say O(1) or some constant time C.

• Now if we have n numbers we need to repeat step 3 for all the n numbers. So overall complexity will be of linear order i.e O(n) which is a polynomial time complexity.