When a divide-and-conquer algorithm...

When a divide-and-conquer algorithm divides an instance of size n of a problem into sub instances 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_i = 1 [a^k - j times g(c^j)], (b) Solve the recurrence relation given that g (n) elementof theta (n)