Multidimensional divide-and-conquer maximin recurrences

Laurent Alonso (1) , Edward M. Reingold , René Schott

1 INRIA Lorraine

Bounds are obtained for the solution to the divide-and-conquer recurrence M (n) = F(max;k1+...+kp = n) (M(k1)+M(k2)+...+M(kp)+min(f(k1),...,f(kp))), for nondecreasing functions f. Similar bounds are found for the recurrence with "min" replaced by "sum-of-all-but-the-max." Such recurrences appear in the analysis of various algorithms.

Mots clés: recurrence relations; divide and conquer; algorithmic analysis

Domaines: Autre [cs.OH]

Laurent Alonso, Edward M. Reingold, René Schott. Multidimensional divide-and-conquer maximin recurrences. [Research Report] RR-1701, INRIA. 1992. ⟨inria-00076938⟩