1. (5 pts) Suppose that that T(n) = 5 for n = 1, and for all...

 

Transcribed Image Text:

1. (5 pts) Suppose that that T(n) = 5 for n = 1, and for all n 2, a power of 7, T(n) = 7T(n/7) + 4n+3. Solve this recurrence exactly by drawing a recursion tree. (You will need to give an exact explicit solution for T, by specifying all coefficient and constant values, do not use 0, 2, or ). You can assume that n = 7' for some non-negative integer i. 2. (5 pts) Suppose that T(n) = 5 for n = 1, and for all n 2, T(n) = T(n-7) + 4n+ 3. Solve this recurrence exactly by drawing a recursion tree. (You will need to give an exact explicit solution for T, by specifying all coefficient and constant values, do not use 0, 2, or ). You can assume that n = 7*i +1 for some non-negative integer i. 1. (5 pts) Suppose that that T(n) = 5 for n = 1, and for all n 2, a power of 7, T(n) = 7T(n/7) + 4n+3. Solve this recurrence exactly by drawing a recursion tree. (You will need to give an exact explicit solution for T, by specifying all coefficient and constant values, do not use 0, 2, or ). You can assume that n = 7' for some non-negative integer i. 2. (5 pts) Suppose that T(n) = 5 for n = 1, and for all n 2, T(n) = T(n-7) + 4n+ 3. Solve this recurrence exactly by drawing a recursion tree. (You will need to give an exact explicit solution for T, by specifying all coefficient and constant values, do not use 0, 2, or ). You can assume that n = 7*i +1 for some non-negative integer i.