Binary-Search(x, A, min, max) 2 3 4 low - min high - max while low Almid] else return mid high - mid -1 8 low mid 1 10 return "NOT FOUND" (The problem involves mathematical equations and drawing diagrams. It is your choice whether to figure out how to do this in Google Docs & Drawing, to do it in your favorite program, or to do your work on paper and scan or photograph it. We prefer that you compile the results in one PDF, but if that is difficult compile them into one zip file.) (a) Write the recurrence relation for BinarySearch, using the formula T(n) - aT(nlb) + D(n) + C(n) (We'll assume T(1)-c, where c is some constant, and you can use c to represent other constants as well, since we can choose c to be large enough to work as an upper bound everywhere it is used.) (b) Draw the recursion tree for BinarySearch, in the style shown in screencast 2E and in Figure 2.5 of CLRS. (Don't just copy the example for MergeSort: it will be incorrect. Make use of the recurrence relation you just wrote!) (c) Using a format similar to the counting argument in Figure 2.5 of the text or of screencast 2E, use the tree to show that BinarySearch is O(lg n) in the worst case. Specifically, 1. 2. 3. show what the row totals are write an expression for the tree height (and justify it), and use this information to determine the total computation represented by the tree