Question

Consider the following algorithm. ALGORITHM Enigma(A[0.n - 1]) //Input: An array A[0.n - 1] of integer numbers for i leftarrow† 0 to n - 2 do for j leftarrow†† i +1 to n - 1 do if A[i] = = A[j] return false return true a) What does this algorithm do? b) Compute the running time of this algorithm.

Answer 1

Algorithm Enigma(A)

for i 0 to n-2

for j=i+1 to n-1

if(A[i] == A[j])

return false;

return true

a. This algorithm is running 2 loops. Outer loop from i = 0 to n-2 and inner loop from i+1 to n-1. For every outer loop element, it is checking whether it is equal to any element from inner loop. So, this algorithm is calculating for the existence of duplicate elements. If there is any duplicate element, it is returning false, else it is returning true

b. Time complexity :

There are two loops.

Inner loop is running n-1 times, n-2 times, .....1 times respectively. So, it is running a total of Sigma(n-1) times which is (n-1)*n/2.

So, time complexity is O(N^2)