Consider the following procedure Gnarly, which returns true or false. Notice the indenting on lines 04-05: they execute only when the test on line 03 succeeds. You can assume that \(n \ge 1\) and that extracting a subarray (e.g. in the recursive calls in line 06) requires only constant time.

01 Gnarly (a[1],..., a[n]: array of integers) 02 if (n = 1) return true 03 else if (n = 2) 04 if (a[1] = a[2]) return true 05 else return false 06 else if (Gnarly(a[1],...,a[n-1]) and Gnarly(a[2],...,a[n])) return true 07 else return false

- If Gnarly returns true, what must be true of the values in the input array? Briefly justify your answer.
- Give a recursive definition for T(n), the running time of Gnarly on an input of length n. Be sure to include a base case.
- Give a big-theta bound on the running time of Gnarly. For full credit, you must show work or briefly explain your answer.

Here is pseudocode for functions find_closest and find_closest_sorted. Each function takes as input an array of n numbers and a target number and outputs the closest value in the input that is at least as large as the target (or NULL if no such number exists). The function find_closest_sorted assumes that the input array is sorted in ascending order.

01 function find_closest(input_array, target)} 02 sorted_array = cocktailsort(input_array) 03 return find_closest_sorted(sorted_array, target) 04 function find_closest_sorted(sorted_array, target) 05 length = get_length(sorted_array) // takes constant time 06 if length = 0 07 return NULL 08 else if length = 1 09 if sorted_array[0] >= target 10 return sorted_array[0] 11 else return NULL 12 else 13 mid = floor(length/2) 14 if (sorted_array[mid-1] < target) 15 half_array = sorted_array(mid,...,length-1) // array containing second half of elements 16 else 17 half_array = sorted_array(0, ...,mid-1) // array containing first half of elements 18 return find_closest_sorted(half_array, target)

Answer the questions below using worst-case analysis (e.g., the target value is equal to the largest number in the input array). Assume that the input length n is a power of 2 and that cocktailsort takes \(\Theta(n^2)\) time.

- Suppose R(n) is the running time of find_closest_sorted. Give a recursive definition of R(n). Assume that it takes constant time to extract the first or second half of the array in lines 15 and 17.
- What is the height of the recursion tree for R(n)?
- How many leaves are in the recursion tree for R(n)?
- What is the big-Theta (aka tight big-O) running time of find_closest_sorted? Make your answer as simple as posible.
- What is the big-Theta running time of find_closest. Make your answer as simple as possible.