Contraction Maps on Complexity Spaces and itExpoDC Algorithms

摘要

We present a mathematical model, based on techniques of Denotational Semantics, for the complexity analysis of itexpoDC algorithms. This is done by showing that the recurrence inequation associated to an itexpoDC algorithm gives rise to a contraction map on a suitable quasi-metric space of complexity functions. We prove that this contraction has a unique fixed point which is the maximal element, with respect the order induced by the quasi-metric, of the set of solutions of the recurrence inequation. The complexity of such an algorithm is represented by this maximal element.