Question

1. Programming Exercise 1

Write a function that will have a list as an input, the task of the function is to check if all the elements in the list are unique,( i.e. no repetition of any value has occurred in the list), then the function returns true otherwise it returns false. Your program should include a main method that call the method to test it.

2. Algorithm Analysis

For the function you implemented in part 1, please calculate T(n), which represents the running time of your algorithm in terms of n. Where n is the length of the list. Then find the order of magnitude of your algorithm (Big O).

3. Algorithms Comparison

Please find another algorithm that solves part 1, write the code, calculate T(n) and find Big O. Then compare the efficiency with the algorithm from part1 to determine the more efficient one.

Answer 1

CODE IN JAVA:

Unique.java file:

import java.util.*;

public class unique {

public static boolean check(int arr[]) {

int n = arr.length;

ArrayList<Integer> uniqueList = new ArrayList<Integer>();

boolean flag = true;

for(int val:arr) {

if(uniqueList.indexOf(val)==-1)

uniqueList.add(val);

else

return false;

}

return true;

}

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner sc = new Scanner(System.in);

int n;

System.out.print("Enter the size of the array:");

n = sc.nextInt();

int arr[] = new int[n];

System.out.println("Enter the elements of the array:");

for(int i=0;i<n;i++) {

arr[i] = sc.nextInt();

}

if(check(arr))

System.out.println("Your array is unique");

else

System.out.println("Your array has duplicate values");

}

}

OUTPUT:

The worst case time complexity of above program is : O(n^2)