The following program computes 2n : int power2(int n) \{ if (n==0) return 1; return power2 (n1)+ power 2(n1); \} (a) Find a recurrence formula as we learned in class. Find the runtime. What is the big problem with this function? (hint: We discussed something similar in class). (b) Introduce a small modification that makes the function run in linear time. Show why the runtime is linear. (c) (bonus) The following function also calculates 2n : int power2New(int n) \{ if (n==0) return 1; if (n%2==0){ int result = power2New (n/2); return result*result; \} else return 2*power 2 New (n1); \} Explanation: If n is even, then 2n=(22n)2, so we can calculate 22n recursively and square, cutting half of n in one move. Otherwise, we resort to the previous method. Show that the runtime of power2New is logarithmic in n. Hint: It's easy to show it when n is even, but sometimes n is odd... The trick is to show that the entire function is logarithmic nonetheless