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

摘要: 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 quasi-metric spaces as a part development topological asymptotic programs algorithms in 1995. applicability this to divide conquer was also illustrated by same paper. In particular, he gave new formal proof, based on use Banach fixed-point theorem, well-known fact that upper bound average running time computing Mergesort belongs class n log 2 . Recently, Schellekens’ method has been shown be useful yielding bounds whose leads recurrence equations different from ones reported Cerda-Uguet et al. Baire partial space: mathematical tool Computer Science Theory Syst. 50 2012, 387–399.]. However, variety can analysed with approach is not much larger than original method. paper, one hand, we extend order yield certain recursive cannot discussed following techniques given and, other improve introducing technique providing, contrary case lower aforementioned those studied We illustrate validate developed applying our results provide celebrated Quicksort, Largetwo Hanoi.