We address the issue of analyzing the complexity of programs written in a
(higher order) programming language. The category Cpo2
is proposed as the appropriate setting for an intensional semantics,
capturing the exact complexity of programs. Complexity estimates,
either in the form of lower or upper bounds, are obtained via abstract
interpretation in a category A of complete lattices. The abstract
and intensional interpretations are related through logical relations.