When a divide-and-conquer algorithm divides an instance of size n of a problem into subinstances each of size n/c, the recurrence relation is typically given by T(n) = aT(n/c) + g(n) for n > 1 T(1) = d where g(n) is the cost of the dividing and combining processes, and d is a constant. Let n = c^k. (a) Show that T(c^k) = d times a^k + sigma^k_j=1 [a^k-j times g(c^j)]. (b) Solve the recurrence relation given that g(n) elementof theta(n)