Estevan, AsierMiñana, Juan-JoséValero, Oscar2024-09-102024-09-102019-10Estevan Asier, Miñana Prats Juan José, Valero Oscar. On fixed point theory in partially ordered sets and an application to asymptotic complexity of algorithms. Rev Real Acad Cienc Exactas Fis Nat Ser A-Mat. 2019 Oct;113(4):3233-3252.1578-7303http://hdl.handle.net/20.500.13003/14764https://hdl.handle.net/20.500.12105/22817The celebrated Kleene fixed point theorem is crucial in the mathematical modelling of recursive specifications in Denotational Semantics. In this paperwe discuss whether the hypothesis of the aforementioned result can be weakened. An affirmative answer to the aforesaid inquiry is provided so that a characterization of those properties that a self-mapping must satisfy in order to guarantee that its set of fixed points is non-emptywhen no notion of completeness are assumed to be satisfied by the partially ordered set. Moreover, the case in which the partially ordered set is coming from a quasi-metric space is treated in depth. Finally, an application of the exposed theory is obtained. Concretely, a mathematical method to discuss the asymptotic complexity of those algorithms whose running time of computing fulfills a recurrence equation is presented. Moreover, the aforesaid method retrieves the fixed point basedmethods that appear in the literature for asymptotic complexity analysis of algorithms. However, our new method improves the aforesaid methods because it imposes fewer requirements than those that have been assumed in the literature and, in addition, it allows to state simultaneously upper and lower asymptotic bounds for the running time computing.engAMhttp://creativecommons.org/licenses/by-nc-nd/4.0/Partial orderQuasi-metricFixed pointKleeneAsymptotic complexityRecurrence equationAttribution-NonCommercial-NoDerivatives 4.0 International11343233-325210.1007/s13398-019-00691-81579-1505Revista de la Real Academia de Ciencias Exactas Fisicas y Naturales Serie A-Matematicasopen access2-s2.0-85066026409483725900020