Given the following recurrence relations, derive their closed forms by drawing a recursion tree and/or using...

   

Transcribed Image Text:

Given the following recurrence relations, derive their closed forms by drawing a recursion tree and/or using algebraic manipulation, and then enter your closed forms in the corresponding textboxes below. R(n) = 1, for n = :0 R(n-1)+2c, for n 1, c N R(n) = 1+2*c*n ? S(n) = 18, for n = 1 | 10S(n 1) + 18n, for n > 1 - |S(n) = = 1810^(n-1) - 16*(1 (-2)^n) - 2*(n-1) ? T(n) = = [3, for n = 1 (2T(n/2) + 3n, for n > 1 T(n) = 3*n*(1+ log(n)) Notes: You may assume that n is a power of 2. To specify log(n), use log(n,b) You may find it helpful to remind yourself how to compute the sum of a geometric series. You may find it helpful to know that 1 kak n-1 be in the form you need, even if it is useful!) = (n-1)an+1-na+a (a-1) (Of course, that equation may not Given the following recurrence relations, derive their closed forms by drawing a recursion tree and/or using algebraic manipulation, and then enter your closed forms in the corresponding textboxes below. R(n) = 1, for n = :0 R(n-1)+2c, for n 1, c N R(n) = 1+2*c*n ? S(n) = 18, for n = 1 | 10S(n 1) + 18n, for n > 1 - |S(n) = = 1810^(n-1) - 16*(1 (-2)^n) - 2*(n-1) ? T(n) = = [3, for n = 1 (2T(n/2) + 3n, for n > 1 T(n) = 3*n*(1+ log(n)) Notes: You may assume that n is a power of 2. To specify log(n), use log(n,b) You may find it helpful to remind yourself how to compute the sum of a geometric series. You may find it helpful to know that 1 kak n-1 be in the form you need, even if it is useful!) = (n-1)an+1-na+a (a-1) (Of course, that equation may not