The algorithm below is for a linear search.

Do the following tasks to analyze the algorithm. Note that using a method is not actually part of the algorithm. You are free to redesign the code however you wish, as long as you use a loop to iteratively search for the target. PLEASE ANSWER ALL THE PARTS.

a. Design a program that does the following:

Create an array of size N that is filled with random integer values from 0 to N-1. This is easy to do using nextInt(n) from the Random class.

Perform the following test for at least 10 trials:

- Choose a random target value from 0 to N-1.

- Find and print the number of iterations required to locate the target. Note that the number of iterations will be the value of the iterator variable when the search loop terminates. If the target value isnt found, that can be treated as N+1 iterations, for simplicity. For example, the following output might be the result using N = 50, where all of the random target values appear in the random array, except 34 and 17 (each with 51 iterations). The value 16 appears at the beginning of the array (1 iteration).

b. Run the program from part (a) for at least 6 evenly spaced N values. You are allowed to manually change the N value and copy the new output each time you run the program. Write the program output for all 6 values of N.

c. Do your results from (b) support the theory that the average run time is O(n)? Explain your answer.

d. Create a single graph, including a legend, using any graphing software you wish with three lines:

Average-case number of iterations vs. N using your experimental results from part (b).

Best-case number of iterations vs. N. (This is determined without using an experiment.)

Worst-case number of iterations vs. N. (This is determined without using an experiment.)

e. What are the Big-O expressions for the following cases? Briefly explain your answers.

Best-case number of iterations.

Worst-case number of iterations.

public static boolean search (double[ ] data, double target) int i for (i 0;