Quasi-metric properties of complexity spaces

The complexity (quasi-metric) space has been introduced as a part of the development of a topological foundation for the complexity analysis of algorithms (Schellekens, 1995). Applications of this theory to the complexity analysis of Divide and Conquer algorithms have been discussed by Schellekens (1995). Here we obtain several quasi-metric properties of the complexity space. The main results obtained are the Smyth-completeness of the complexity space and the compactness of closed complexity spaces which possess a (complexity) lower bound. Finally, some implications of these results in connection to the above mentioned complexity analysis techniques are discussed and the total boundedness of complexity spaces with a lower bound is discussed in the Light of Smyth's computational interpretation of this property (Smyth, 1991). (C) 1999 Elsevier Science B.V. All rights reserved.