The automatic complexity analysis of divide-and-conquer algorithms

Abstract : Current tools performing automatic complexity analysis are capable to deal with function definitions based on structural induction. Divide-and-conquer algorithms with "intelligent" divide function (like quicksort) are not based on structural induction, but on noetherian induction. This paper presents a method of automatic complexity analysis to deal with such kinds of functions.
Type de document :
Rapport
[Research Report] RR-1149, INRIA. 1989
Liste complète des métadonnées

https://hal.inria.fr/inria-00075410
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 18:09:46
Dernière modification le : vendredi 16 septembre 2016 - 15:11:37
Document(s) archivé(s) le : dimanche 4 avril 2010 - 21:50:45

Fichiers

Identifiants

  • HAL Id : inria-00075410, version 1

Collections

Citation

Paul Zimmermann, Wolf Zimmermann. The automatic complexity analysis of divide-and-conquer algorithms. [Research Report] RR-1149, INRIA. 1989. 〈inria-00075410〉

Partager

Métriques

Consultations de la notice

191

Téléchargements de fichiers

248