The complexity probabilistic quasi-metric space (Q624638): Difference between revisions

A probabilistic complexity quasi-metric space, as a fuzzy extension of the complexity quasi-metric space of \textit{M. P. Schellekens} [The Smyth completion: A common foundation for denotational semantics and complexity analysis. Elec. Notes Theoret. Comput. Sci. 1, 535--556 (1995; Zbl 0910.68135)] is constructed. This probabilistic complexity quasi-metric space improves Schellekens' approach by providing an appropriate setting to obtain a suitable measurement of the distance from a complexity function \(f\) to another one \(g\), when \(f\) is asymptotically more efficient than \(g\). A version of \textit{V. Gregori} and \textit{A. Sapena}'s fixed point theorem [Fuzzy Sets Syst. 125, No.~2, 245--252 (2002; Zbl 0995.54046)] for quasi-Menger spaces, with applications to functionals associated both to Divide and Conquer algorithms and Quicksort algorithms is also given.