Determine the worst-case running time of the following functions, using big-Theta notation. Show your work by describing the running time of each line, as we have done in lecture.

2) Add statements to the code that outputs the number of times the inner-most loop is iterated. Answer the following questions:

a. What type of input allows the algorithm to terminate without an error and results in the worst-case running time? (examples: array sorted in ascending order, array sorted in descending order, unique values, duplicate values, etc.)

b. Create arrays that will produce the worst-case behavior with the following sizes (100, 1000, 10000). Provide these arrays as arguments to the methods, and fill in the following table.

Array Size Number of Iterations of the inner-most loop 100 1,000 10,000 c. Argue that the results that you showed in part b are consistent with the analysis you gave in part 1.

void func2(double[] array) { for (int x=1; x < array.length; x++) { for (int y=0; y < array.length-x; y++) { if (array[y] > array[y+1]) { double tmp = array[y]; array[y] = array[y+1]; array[y+1] = tmp; } } } }

void func3(int[] array) { int ndx = 0; while (ndx >= 0) { array[ndx] = array[ndx] - 1; ndx = array[ndx]; } } double func4(int[] array) { double y_hat = 0; for (int x=0; x < array.length && x < 10_000; x++) { y_hat = (array[x] + x*y_hat) / (x+1); } return y_hat; }