Consider the recurrence relation T(n) = T([n/2J) + T([n/2l) + bn^2, if n greaterthanorequalto 2 T(1) = e(1) Assuming that n is a power of 2, use a recursion tree to solve this recurrence. The answer is not 0(n2logn). (You might find the following useful: if r notequalto 1, then Sigma^n_i = 0 r^i = (r^n + 1 - 1)/(r - 1).) (20%) Use induction to prove that the upper bound you obtained in the previous exercise holds in the general case, when n is not necessarily a power of 2. (Do only the upper bound.)