Abstract
Let M(n) be defined by the recurrence M(n) = max (M(k) + M(n - k) + min(f(k), f(n - k))), 1≤k<n where f is an arbitrary nondecreasing function and M(1) is given. The recurrence M(n) is a divide-and-conquer maximin recurrence, which occurs in a variety of problems in the analysis of algorithms. In this paper, a new upper bound on M(n) is first derived. The derived bound is smaller than the one proposed previously by Li and Reingold. It is at most two times the exact solution of M(n). Using the bound, we further show that M(n) ≤ 2E(n), where E(n) is defined by the recurrence E(n) = E(⌊n/2⌋) + E(⌈n/2⌉) + f(⌊n/2⌋). From this result, we can conclude that a divide-and-conquer algorithm whose time complexity is expressed as M(n) is as efficient as a divide-and-conquer algorithm whose time complexity is expressed as E(n). © 1997 Academic Press.