3. The following program computes 2: int power2(int n) { } if (n= 0) return 1;...

 

Transcribed Image Text:

3. The following program computes 2": int power2(int n) { } if (n= 0) return 1; return power2(n-1)+power2(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 power2New (int n) { } if (n= 0) return 1; if (n % 2 == 0) { } int result = power2New (n/2); return result*result; else return 2*power2New (n-1); Explanation: If n is even, then 2" = (2)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. 3. The following program computes 2": int power2(int n) { } if (n= 0) return 1; return power2(n-1)+power2(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 power2New (int n) { } if (n= 0) return 1; if (n % 2 == 0) { } int result = power2New (n/2); return result*result; else return 2*power2New (n-1); Explanation: If n is even, then 2" = (2)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.

Answer rating: 100% (QA)

a The recurrence formula for the original power2 function is Tn 2Tn1 1 where Tn represents the time ... View the full answer