• Find Θ(T (n)) for each case. • For problem 1, find the solution three ways: { The master theorem { The substitution method { Iterate, cancel, and solve the summation to find an exact solution. • For all other problems, use just the master theorem. • When using the master theorem, be explicit about nlogb a, and about which case of the master theorem applies, about making sure the special condition applies in case 3 of the master theorem, and about proving f’s correct asymptotic relationship to nlogb a. 1. Solve this one three different ways: master theorem, substitution method, and the iterate/cancel/summation method. T (n) = 2T (n=2) + n4 2. Solve this one using the master theorem. T (n) = 16T (n=4) + n2 3. Solve this one using the master theorem. T (n) = 2T (n=4) + pn 4. Solve this one using the master theorem. T (n) = 4T (n=3) + n lg n 5. Solve this one using the master theorem. T (n) = 4T (n=2) + n2pn 1
