Hi, I needed some help with this problem. Unfortunately no-one was able to help, so hoping someone else can. If you can provide me with some steps, and instructions, that would be great so that I can work myself backwards from the solution and understand what I'm doing. Thank you so much! Runtime (Binary Search) This problem steps you through a recursion tree analysis of BinarySearch to show that it is (lg n) in the worst case. (The problem involves mathematical equations and drawing diagrams) (a) Write the recurrence relation for BinarySearch, using the formula T(n) = aT(n/b) + 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 Figure 2.5 (below). Don't copy it, just use as an example! Make to use of the recurrence relation you just wrote.

(c) Using a format similar to the counting argument in Figure 2.5 use the tree to show that BinarySearch is (lg n) in the worst case. Specifically,

1. show what the row totals are,

2. write an expression for the tree height (and justify it), and

3. use this information to determine the total computation represented by the tree. Thank you!

Binary-Search(x, A, min, max) 2 3 4 2 highmax while low