Calculate running time of a divide-and-conquer algorithm .
'''Originally Posted By: dburke'''
Let T(n) be the running time on a problem of size n.<br><br>If the problem size n&le;c for some constant c, we assume the problem falls into the straightforward solution case and so take time &Theta;(1).<br><br>Suppose that the division of the problem yields a subproblems, each of which is 1/b the size of the original.<br><br>Then it takes T(n/b) time to solve one subproblem of size n/b, and so it takes aT(n/b) time to solve a of them.<br><br>Suppose it takes D(n) time to divide the problem into subproblems and C(n) time to combine the solutions to the subproblems. Then the total time to solve the problem is:<br>Code: &nbsp; &nbsp; &nbsp; &nbsp; <br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &Theta;(1)&nbsp; &nbsp; &nbsp; if n &le; c<br>T(n)=&nbsp; &nbsp;<br>&nbsp; &nbsp; &nbsp; &nbsp; a T(n/b)+D(n)+C(n) otherwise<br>&nbsp; &nbsp; &nbsp; &nbsp;