Exact balancing is not always good
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.
analysis of divide- and-conquer algorithms
scientific article; zbMATH DE number 3943018