4. (a) Fill in the '?' to make the following statement true. n T(n) = 1.01 i=1 -i = O(?). (b) Use a recursion tree to compute an asymptotic solution for the recurrence G(n)G(2n/3) + G(n/3) +n. 5. Give asymptotic bounds for T(n) in each of the following recurrences. Assume any reasonable base cases in the recurrences below, for example, T(n) is constant for n ≤ 2. Make your bounds as tight as possible, and justify your answers. (a) T(n) = 9T(n/3) + 225n (b) T(n)T(9n/10) + log n (c) T(n) = 3T(n/2) + n² √n (d) T(n) = T(n − 1) + n²

4. (a) Fill in the '?' to make the following statement true. n T(n) = 1.01 i=1 -i = O(?). (b) Use a recursion tree to compute an asymptotic solution for the recurrence G(n)G(2n/3) + G(n/3) +n. 5. Give asymptotic bounds for T(n) in each of the following recurrences. Assume any reasonable base cases in the recurrences below, for example, T(n) is constant for n ≤ 2. Make your bounds as tight as possible, and justify your answers. (a) T(n) = 9T(n/3) + 225n (b) T(n)T(9n/10) + log n (c) T(n) = 3T(n/2) + n² √n (d) T(n) = T(n − 1) + n²