Abstract
In Cerda-Uguet et al. (Theory Comput. Syst. 50:387-399, 2012), a new mathematical fixed point technique, that uses the so-called Baire partial quasi-metric space, was introduced with the aim of providing the asymptotic complexity of a class of recursive algorithms. The aforementioned technique presents the advantage that requires less calculations than the quasi-metric original one given by Schellekens (Electron. Notes Theor. Comput. Sci. 1:211-232, 1995). In this paper we continue the study, started in Cerda-Uguet et al. (Theory Comput. Syst. 50: 387-399, 2012), on the use of partial quasi-metric spaces for asymptotic complexity analysis of algorithms. Concretely, our main purpose is to prove that the Baire partial quasi-metric space is an appropriate mathematical framework for discussing via fixed point arguments the asymptotic complexity of a general class of recursive algorithms to which all the algorithms analyzed in Cerda-Uguet et al. (Theory Comput. Syst. 50: 387-399, 2012) belong. The obtained results are illustrated by means of applying them to yield the complexity of two celebrated recursive algorithms which don not belong to the class discussed in Cerda-Uguet et al. (Theory Comput. Syst. 50:387-399, 2012).