Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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 (Research report)
Complete list of metadata
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 6:09:46 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:34 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:50:45 PM


  • HAL Id : inria-00075410, version 1



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



Record views


Files downloads