1. [5 pts] f(n) satisfies the recurrence equation Big- notation for f(n). Hint: Let an =...

   

Transcribed Image Text:

1. [5 pts] f(n) satisfies the recurrence equation Big- notation for f(n). Hint: Let an = f(n) f(n-1) n+1 = 1 + n n+1 with f(1) = (1), give a f(n) n+1' 1 f(1) then an = An-1 + with a = = (1). Then n+1 2 1 1 1 an = + + + + = (Inn), and f(n) = (n + 1)an. n+1 n 2. [5 pts] Let T(n) = 3T) + (n) and (n) = O(n), use the mater method to solve T(n). 1. [5 pts] f(n) satisfies the recurrence equation Big- notation for f(n). Hint: Let an = f(n) f(n-1) n+1 = 1 + n n+1 with f(1) = (1), give a f(n) n+1' 1 f(1) then an = An-1 + with a = = (1). Then n+1 2 1 1 1 an = + + + + = (Inn), and f(n) = (n + 1)an. n+1 n 2. [5 pts] Let T(n) = 3T) + (n) and (n) = O(n), use the mater method to solve T(n).