CSCI 305, Homework # 3
• 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) +√n
4. Solve this one using the master theorem.
T(n) = 4T(n/3) + nlgn
5. Solve this one using the master theorem. T(n) = 4T(n/2) + n2√n
