Question. A particular divide-and-conquer algorithm, when run on an input of size n, works by spending Θ(n) time splitting the problem in half, then does a recursive call on each half, then spends Θ(n2) time combining the solutions to the recursive calls. On small inputs, the algorithm takes a constant amount of time. To within a constant factor, how long does this algorithm take, in terms of n?
Answer. The recurrence is T(n) = 2T(n/2) + Θ(n2). The solution is T(n) = Θ(n2).