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
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.