Romaguera Bonilla, S.; Tirado Peláez, P. (2011). The complexity probabilistic quasi-metric space. Journal of Mathematical Analysis and Applications. 376:732-740. https://doi.org/10.1016/j.jmaa.2010.11.056
Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/31444
Title:
|
The complexity probabilistic quasi-metric space
|
Author:
|
Romaguera Bonilla, Salvador
Tirado Peláez, Pedro
|
UPV Unit:
|
Universitat Politècnica de València. Departamento de Matemática Aplicada - Departament de Matemàtica Aplicada
|
Issued date:
|
|
Abstract:
|
[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 ...[+]
[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.
[-]
|
Subjects:
|
Algorithm
,
Asymptotic
,
Bicomplete
,
Complexity function
,
Contractive
,
Fixed point
,
Functional
,
Probabilistic quasi-metric
,
Quasi-Menger space
,
Smyth complete
|
Copyrigths:
|
Cerrado |
Source:
|
Journal of Mathematical Analysis and Applications. (issn:
0022-247X
)
|
DOI:
|
10.1016/j.jmaa.2010.11.056
|
Publisher:
|
Elsevier
|
Publisher version:
|
http://dx.doi.org/10.1016/j.jmaa.2010.11.056
|
Project ID:
|
info:eu-repo/grantAgreement/MICINN//MTM2009-12872-C02-01/ES/Construccion De Casi-Metricas Fuzzy, De Distancias De Complejidad Y De Dominios Cuantitativos. Aplicaciones/
|
Thanks:
|
The authors acknowledge the support of the Spanish Ministry of Science and Innovation under grant MTM2009-12872-C02-01.
|
Type:
|
Artículo
|