Discrete Structures/Math

Problem 2 20 pts (10 pts each)]: 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 algorithm's running time, then find a closed-form equation. Show your solution is correct by showing that it obeys the recurrence