Question

Question 4 6 points You have to design an algorithm that verify if an array contains duplicate values. This algorithm simply returns true as soon as two identical values are found. To perform this task you must not change the order of the elements in the array (so you cannot sort it) or use an auxiliary array. Write the pseudo-code of this algorithm and give the Big-2 complexity in the worst case.

Answer 1

Algorithm:

=>In this A is an array of size n.Array index starts at 1 and ends at n

Duplicates(A,n)

for(i=1 to n-1)                         //this is for checking whether the i th index value has duplicate or not

      for(j=i+1 to n)                 //from next value of ith index to nth index loop

           if(A[i]==A[j])             //comparing if the values are same

                  return "True"       //returning true of equals

return "False"                       //if this came our of 2 loops it means that there are no duplicates hence

                                             //returning False

Time complexity:

Worst case : Ω(n²)

Ex: A[6]={1,2,3,4,5,6} it will find that there are no duplicates.

      => The inner loop iterates sum of natural numbers times i.e., (n)(n-1)/2 => n²-n/2

      => n-1,n-2,n-3,n-4,.........,1 times the inner loop iterations.

      =>n² is major term so the time complexity will take that.