1). Recurrences

i. Solve the recurrence T (N ) = 4T (N/2) + N, T (1) = 1 for a closed-form solution by repeated substitution. Show your solution is correct by showing that it obeys the recurrence.

ii. An algorithm runs recursively on the first half of its data, then runs recursively on the second half of its data, and then takes 1 step to use the results of these recursive calls. The base case also takes 1 step. Write a recurrence that describes this algorithms running time, then find a closed-form equation. Show your solution is correct by showing that it obeys the recurrence.