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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00075410
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 6:09:46 PM
Last modification on : Friday, September 16, 2016 - 3:11:37 PM
Long-term archiving on : Sunday, April 4, 2010 - 9:50:45 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

269

Files downloads

431