Question 9 : 10 points Solve the following Recursive Relationships. Show your expansion and give the Big Oh result. Here is an example using Binary Search. We have T(n) = T(n/2) + 1 and T(1) = 1. Example Answer: Expand the pattern into an expression in terms of k. T(n) =T(n/2) + 1 =T(n/4) + 2 =T(n/8) + 3 =T(n/16) + 4 =T(n/2 k ) + k The expression T(n/2 k ) hits T(1) when k = log2 (n). Plug in T(n) =T(n/2 log2(n) ) + log2 (n) =T(n/n) + log2 (n) =1 + log2 (n) The function is T(n) = O(log2 (n)). END EXAMPLE ANSWER (a) (5 points) T(n) = T(n 1) + 1 and T(1) = 1 (b) (5 points) T(n) = 3T(n/3) + n and T(1) = 1