ACE: an automatic complexity evaluator. There has been a great deal of research done on the evaluation of the complexity of particular algorithms; little effort, however, has been devoted to the mechanization of this evaluation. The ACE (Automatic Complexity Evaluator) system is able to analyze reasonably large programs, like sorting programs, in a fully mechanical way. A time-complexity function is derived from the initial functional program. This function is transformed into its nonrecursive equivalent according to MacCarthy’s recursion induction principle, using a predefined library of recursive definitions. As the complexity is not a decidable property, this transformation will not be possible in all cases. The richer the predefined library is, the more likely the system is to succeed. The operations performed by ACE are described and the use of the system is illustrated with the analysis of a sorting algorithm. Related works and further improvements are discussed in the conclusion.
Keywords for this software
References in zbMATH (referenced in 9 articles )
Showing results 1 to 9 of 9.
- Chan, Hing Lun; Norrish, Michael: Mechanisation of the AKS algorithm (2021)
- Charguéraud, Arthur; Pottier, François: Verifying the correctness and amortized complexity of a union-find implementation in separation logic with time credits (2019)
- Nipkow, Tobias; Brinkop, Hauke: Amortized complexity verified (2019)
- Charguéraud, Arthur; Pottier, François: Machine-checked verification of the correctness and amortized complexity of an efficient union-find implementation (2015)
- Albert, Elvira; Arenas, Puri; Genaim, Samir; Puebla, German; Zanardini, Damiano: Cost analysis of object-oriented bytecode programs (2012)
- Albert, Elvira; Arenas, Puri; Genaim, Samir; Puebla, Germán: Closed-form upper bounds in static cost analysis (2011)
- Albert, Elvira; Arenas, Puri; Genaim, Samir; Puebla, Germán: Cost relation systems: a language-independent target language for cost analysis (2009) ioport
- Benzinger, Ralph: Automated higher-order complexity analysis (2004)
- Flajolet, Philippe; Salvy, Bruno; Zimmermann, Paul: Automatic average-case analysis of algorithms (1991)