< Back to previous page

Publication

Complexity Analysis via Approach Spaces

Journal Contribution - Journal Article

Complexity of a recursive algorithm typically is related to the solution to a recurrence equation based on its recursive structure.
For a broad class of recursive algorithms we model their complexity in what we call the complexity approach space,
the space of all functions in X = ]0,\infty]^Y, where Y can be a more dimensional input space. The set X, which is a dcpo for the pointwise order, moreover carries the complexity approach structure.
There is an associated selfmap Phi on the complexity approach space X such that the problem of solving the recurrence equation is reduced to finding a fixed point for Phi.
We will prove a general fixed point theorem that relies on the presence of the limit operator of the complexity approach space X and on a given well founded relation on Y.
Our fixed point theorem deals with monotone selfmaps Phi that need not be contractive.
We formulate conditions describing a class of recursive algorithms that can be treated in this way.
Journal: Appl. Categ. Struct.
ISSN: 0927-2852
Issue: DOI 10.1007/s10485-013-9302-2
Volume: 22
Pages: 119-136
Publication year:2014
Keywords:complexity, fixed point
  • Scopus Id: 84894325777