6. The following program computes 2n: int pover2(int n) if (n--o) return 1; return pover2(n-1)+pover2(n-1) (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 2" int pover2Hew(int n) if (n-0) return 1; if(n % 2,,0) { int result power2New(n/2); return result result; else return 2 pover2Nev (n-1); Explanation: If n is even, then 2n-(29)2 so we can calculate 2 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