Big Oh for a recursive function. The following program computes 2ⁿ:

int power2(int n) { if (n==0) return 1; return power2(n-1)+power2(n-1); }

1. Find a recurrence formula as we learned in class, i.e., T(n) in terms of T(n-1). Find the runtime. What is the big problem with this function, something you can see by just looking at this code? (hint: We discussed something similar in class).

2. Introduce a small modification that makes the function run in linear time. Show why the runtime is linear.