(12 points) Solve the recurrence relations below. Indicate which strategy you are using and show your work. Big-theta or exact answer required? Big-theta. On any problem where it is appropriate to use the Master Theorem, big-theta is sufficient (you can't get better from the theorem). But if the master theorem doesn't apply for a certain problem (hint, hint), you'll have to use another technique like telescoping, or filling out a table and doing guess and check. And then you'll have an exact answer anyway on your way to getting big-theta. So write the exact answer too as part of your solution.

1. T(1) = 1, T(N) = 2 T(N/4) + N^0.5

2. T(1) = 1, T(N) = T(N - 2) + 2, assuming N is odd.

3. T(1) = 1, T(N) = 3 T(N/2) + 2N