[25 pts] We wish to search for a value v in a sorted array A of length n. (a) (10 pts] If we let T(n) denote the worst-case number of comparisons required for a basic balanced binary search, then Tin) satisfies a recurrence (up to rounding-off) of T(n) =T(n^2) +1, T(2) = 2 Find an exact solution to the recurrence (1) when n is a power of 2. Suppose we want to modify binary search in the following way: split the array into 3 equal-sized parts instead of 2, by comparing to the (n/3)-rd largest and the (2n/3)-rd large third of the array could contain w, and then recursively search the appropriate third in the same manner. The algorithm terminates when either v is found, or we reach an array of length 3 or less which is just brute-force sequentially searched (b) [5 pts] Set up a recursion with initial condition for S(n), the worst-case number of comparisons required to search an array this way (again, ignoring rounding-off). (c) [10 pts) Find the solution S(n) to this recurrence when n is a power of 3, and compare it to your answer from (a) by finding lim - sm to 3 decimal places