Question

Describe an efficient recursive algorithm for solving the element uniqueness problem, which runs in time that is at most O(n²) in the worst case without using sorting.

 

 

Answer 1

The problem can be solved in O(n2) using two for loops in cas cade whick gives the function an O(n2) wihtout the usage of sorting of elements.

 

Algorithm:

The algorithm will return “j” or true of the element its in the array are unique and return “O” of the elements are not unique.

 

A is the input array containing the elements from index 0 to (n – 1)

for (i = 0; I <= (n-1); i++)

{

For (j = i + 1; j <= (n-1); j ++)

{

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

Return 0;

Break

}

}

The problem can be solved in O(n2) using two for loops in cas cade whick gives the function an O(n2) wihtout the usage of sorting of elements.