The Smyth Completion A Common Foundation for Denotational Semantics and Complexity Analysis

AbstractThe Smyth completion ([15], [16], [18] and [19]) provides a topological foundation for Denotational Semantics. We show that this theory simultaneously provides a topological foundation for the complexity analysis of programs via the new theory of “complexity (distance) spaces”. The complexity spaces are shown to be weightable ([13], [8], [10]) and thus belong to the class of S-completable quasi-uniform spaces ([19]). We show that the S-completable spaces possess a sequential Smyth completion. The applicability of the theory to “Divide & Conquer” algorithms is illustrated by a new proof (based on the Banach theorem) of the fact that mergesort has optimal asymptotic average running time