4. Consider the following function: int f (int n) { if (n= 0) return 2; else...

    

Transcribed Image Text:

4. Consider the following function: int f (int n) { if (n= 0) return 2; else if (n=1) return 5; else{ int val = 2*f (n-1); val = val - f (n-2); } } return val; (a) Write a recurrence relation for the value returned by f. Solve the recurrence exactly. (Don't forget to check it) (b) Write a recurrence relation for the running time of f. Get a tight upperbound (i.e. big-O) on the solution to this recurrence. 2 4. Consider the following function: int f (int n) { if (n= 0) return 2; else if (n=1) return 5; else{ int val = 2*f (n-1); val = val - f (n-2); } } return val; (a) Write a recurrence relation for the value returned by f. Solve the recurrence exactly. (Don't forget to check it) (b) Write a recurrence relation for the running time of f. Get a tight upperbound (i.e. big-O) on the solution to this recurrence. 2