Table 6.21 Solutions to Recurrence Relations 6.9 Solutions to Recurrence Relations T(1) = a, and T(n) = b n + C + D Tin/p), where p > 1, d> 0 Condition General Solution d=p T(n)= bn logp n + a+ d=1 a- bp T(n)= n + c logp n + p-1 T(n)=clogp n + a bp p-1 d = 1, b = 0 d#1,dp T(n)= a + log, d d-p d-1 5. Give the O-notation for each of the four general solutions listed in Table 6.21. 6. Show how Equation 6.8 for merge sorting falls out as a special case of the first line of Table 6.21