41 Recurrence examples Give asymptotic upper and lower bound

4-1 Recurrence examples Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n 2. Make your bounds as tight as possible, and justify your answers.

Solution

Solution :

( g )

T(n) = T(n - 1) + n. In this case the master method does not apply, but you can draw a recursion tree and obtain T(n) = (n²).

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------

( h )

T(n) = T(n) + 1. The master method doesn’t apply here either, but by drawing a recursion tree you can see that T(n) = (lg lg n).