1. The following class of recurrences often arise in analysis of divide-and-conquer algorithms. (Note a, b,c, d and are constants; and n is an integer power of b, n b*) T(n T(n/b) +en*, n>1 d, Let h log,a. We used repeated substitution method to derive the solution: An'tBnh log n 6(nh log n), h where A and B are some constants for each case. (A slightly different and more general version of this class of recurrences is presented in various textbooks and is commonly known as Master Theorem.) Use the above formula to find the solution form for each of the following recurrences, where n is a power of 2. Express the solution for invloving constants A and B. (Dou't bother to find the constants.) Then exprssi) form. (a) T(n) 2T(n/2) + 1 (b) T(n)-2T(n/2) + n (c) T(n) 2T (n/2) n2 (d) T(n) = T(n/2) + 1