Description
Q1 Mysterious Function (30 point) What’s the worst case runtime of the following function? Please remember to define n, provide a tight upper bound. public static void mystery1(int z) { System.out.println(z); if (z >= 10) { mystery1(z/10); System.out.println(z); } } Q2 Exponentiation (Fast?) (40 points) ● What’s the best case, worst case, and average-case runtime of pow? Assume n = power. Please remember to define n, provide a tight upper bound. algorithm pow Input: positive integer b, non-negative integer p Output: computing b^p (i.e. b raised to power of p) if p = 0 return 1 else if p = 1 return b else if p is even temp = pow(b, p / 2) return temp * temp else return b * b * pow(b, p-2) Q3 QuickSort (30 point) Given the QuickSort implementation from class, provide an 18-element list that will take the least number of recursive calls of QuickSort to complete. As a counter-example, here is a list that will cause QuickSort to make the MOST number of recursive calls: public static List input() { return Arrays.asList(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0); } And here’s the QuickSort algorithm, for convenience: algorithm QuickSort Input: lists of integers lst of size N Output: new list with the elements of lst in sorted order if N < 2 return lst pivot = lst[N-1] left = new empty list right = new empty list for index i = 0, 1, 2, … N-2 if lst[i] <= pivot left.add(lst[i]) else right.add(lst[i]) return QuickSort(left) + [pivot] + QuickSort(right)