The author studies the following recurrence relation:

:.LV0 :.VU :.OC :.HB M_f(0) = 0,:.HT :.HB M_f(n + 1) = f(n + 1) + :.HS min

_i+j=n

:.HS (M_f(i) + M_f(j)),:.HT :.OE occurring in the analysis of divide-and-conquer algorithms. In case of a strictly convex function f, this relation has a unique solution (due to Fredman and Knuth [1]). The present paper shows that the above assertion is still valid if we replace strict convexity by strict concavity. Furthermore, a “balancing principle” is approximately true in general:

M_f(n − 1) = f(n − 1) + M_f(i − 1) + M:- 0If(n − i − 1),

for some n/3 ≤9Ti ≤9T2n/3.

To develop its argument, the author associates to the above recurrence relation an optimization problem on binary trees.