1. Engineering
  2. Computer Science
  3. i have a question related to textbook data structures and...

Question: i have a question related to textbook data structures and...

Question details

I have a question related to Textbook: Data Structures and Algorithms in Java- Chapter 4 - exercise 63P. The solution posted is unclear and not specific.

This is the exercise 63P:

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.

With unique1 and unique2 as follows:

1Returns true if there are no duplicate elements in the array. * 2 public static boolean unique1 (int ] data) 3 int n data.length; 4 for (int j-0; j< n-1:+) 5 for (int k-j+1; k < n; k++) if (dataj] - data[k]) //found duplicate pair // if we reach this, elements are unique return false; 8 return true;

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

What I want to know is how to calculate the largest value of n. Additionally, while writing program to do experimental analysis, since the two algorithms are used to define uniqueness of elements in array, do we need to initialize array with elements each time the test run to determine its run time?

Right now, what I do is calculating elapsed time of each execution and checking to see if it reaches 60000ms. However, the program takes long time to run and I feel it is not an efficient way to handle this problem. It's clear that both running time of the two algorithms can be expressed in the form of Big-Oh notation. Should we make use of asymptotic analysis in the form of Big-Oh to solve this problem and how?

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution