Java

For each of the algorithms unique1 and unique2, which solve the element uniqueness problem, perform an experimental analysis to determine the largest value of n such that the given algorithm runs in one minute or less. Hint: Do a type of binary search to determine the maximum effective value of n for each algorithm.

public static boolean unique1(int[] data) { int n = data.length; for (int j=0; j < n-1; j++) for (int k=j+1; k < n; k++) if (data[j] == data[k]) return false; // found duplicate pair return true; // if we reach this, elements are unique }

/** Returns true if there are no duplicate elements in the array. */ public static boolean unique2(int[] data) { int n = data.length; int[] temp = Arrays.copyOf(data, n); // make copy of data Arrays.sort(temp); // and sort the copy for (int j=0; j < n-1; j++) if (temp[j] == temp[j+1]) // check neighboring entries return false; // found duplicate pair return true; // if we reach this, elements are unique }