Abstract
In this paper, upper bounds are presented for the solution of the following multidimensional divide-and-conquer maximin recurrence (formula presented) where p≥2, 1≤k<p, f is an arbitrary nondecreasing function, and "smin <sup>(k)</sup> <sub>1≤i≤p</sub> f(n <sub>i</sub> )" denotes "the sum of the smallest k numbers among f(n <sub>1</sub> ), f(n <sub>2</sub> ),..., and f(n <sub>p</sub> )". All the presented upper bounds are at most [log <sub>2</sub> k] + p times the exact solution of G(n). The derivation of the upper bounds is based on properties of partition trees. For k = 1 and k = p - 1 we obtain, respectively, two of the recurrences previously studied by Alonso et al. (SIAM J. Discrete Math. 8 (1995) 428-447). In both of these two cases, our results improve theirs. © 2000 Published by Elsevier Science B.V. All rights reserved.