Multidimensional divide-and-conquer maximin recurrences

Abstract : 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.
Type de document :
Rapport
[Research Report] RR-1701, INRIA. 1992
Liste complète des métadonnées

https://hal.inria.fr/inria-00076938
Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 29 mai 2006 - 11:38:57
Dernière modification le : samedi 17 septembre 2016 - 01:06:48
Document(s) archivé(s) le : vendredi 13 mai 2011 - 22:07:41

Fichiers

Identifiants

  • HAL Id : inria-00076938, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

238

Téléchargements de fichiers

73