New results on the mathematical foundations of asymptotic complexity analysis of algorithms via complexity spaces

Abstract

Schellekens [The Smyth completion: A common foundation for denotational semantics and complexity analysis, Electron. Notes Theor. Comput. Sci. 1 (1995), pp. 211–232.] introduced the theory of complexity (quasi-metric) spaces as a part of the development of a topological foundation for the asymptotic complexity analysis of programs and algorithms in 1995. The applicability of this theory to the asymptotic complexity analysis of divide and conquer algorithms was also illustrated by Schellekens in the same paper. In particular, he gave a new formal proof, based on the use of the Banach fixed-point theorem, of the well-known fact that the asymptotic upper bound of the average running time of computing of Mergesort belongs to the asymptotic complexity class of nlog ₂ n. Recently, Schellekens’ method has been shown to be useful in yielding asymptotic upper bounds for a class of algorithms whose running time of computing leads to recurrence equations different from the divide and conquer ones reported in Cerdà-Uguet et al. [The Baire partial quasi-metric space: A mathematical tool for the asymptotic complexity analysis in Computer Science, Theory Comput. Syst. 50 (2012), pp. 387–399.]. However, the variety of algorithms whose complexity can be analysed with this approach is not much larger than that of algorithms that can be analysed with the original Schellekens method. In this paper, on the one hand, we extend Schellekens’ method in order to yield asymptotic upper bounds for a certain class of recursive algorithms whose running time of computing cannot be discussed following the techniques given by Cerdà-Uguet et al. and, on the other hand, we improve the original Schellekens method by introducing a new fixed-point technique for providing, contrary to the case of the method introduced by Cerdà-Uguet et al., lower asymptotic bounds of the running time of computing of the aforementioned algorithms and those studied by Cerdà-Uguet et al. We illustrate and validate the developed method by applying our results to provide the asymptotic complexity class (asymptotic upper and lower bounds) of the celebrated algorithms Quicksort, Largetwo and Hanoi.

Keywords:

• quasi-metric
• complexity space
• fixed point
• improver
• worsener
• complexity class
• Quicksort
• Hanoi
• Largetwo

2010 AMS Subject Classifications::

• 47H10
• 54E35
• 54E50
• 68Q25
• 68Q30

Acknowledgement

The authors are thankful for the support from the Spanish Ministry of Science and Innovation, grant MTM2009-12872-C02-01.