(5 points) Solve the following recurrence relation: T(1) = 1,
T(N) = T(N-2) + 2, assuming N is odd.
(5 points) Consider the following code. Write a recurrence
relation capturing the work done and solve it. Assume that multiplying
two terms takes constant time.
long power(long x, long n) {
if (n == 0) return 1; return x * power(x, n -
1); }
(12 points) Solve the recurrence relations below using the Master
theorem. Indicate which case of the master theorem you are
using. Express the "non-recursive" portion in terms of big-theta and
also express the final big-theta runtime.
On any problem for which the master theorem cannot be applied, state
this fact. You do not have to solve those problems.