Exact balancing is not always good (Q1072369)

The following recurrence relation frequently occurs in the analysis of divide-and-conquer algorithms: \[ M_ f(0)=0,\quad M_ f(n+1)=f(n+1)+\min_{i+j=n}(M_ f(i)+M_ f(j)). \] In these applications, f is the cost of merging two subproblems, wereas \(M_ f(i)\) and \(M_ f(j)\) are the costs of solving each subproblem; f is monotonic nondecreasing. In this paper we consider such recurrences, when f is not assumed to be convex.