The complexity probabilistic quasi-metric space

[EN] We introduce and study a probabilistic quasi-metric on the set of complexity functions, which provides an efficient framework to measure the distance from a complexity function f to another one g in the case that f is asymptotically more efficient than g. In this context we also obtain a version of the Banach fixed point theorem which allows us to show that the functionals associated both to Divide and Conquer algorithms and Quicksort algorithms have a unique fixed point. © 2010 Elsevier Inc.The authors acknowledge the support of the Spanish Ministry of Science and Innovation under grant MTM2009-12872-C02-01.Romaguera Bonilla, S.; Tirado Peláez, P. (2011). The complexity probabilistic quasi-metric space. Journal of Mathematical Analysis and Applications. 376:732-740. doi:10.1016/j.jmaa.2010.11.056S73274037