Abstract :
Schellekens [M. Schellekens, The Smyth completion: A common foundation for denotational
semantics and complexity analysis, in: Proc. MFPS 11, in: Electron. Notes Theor. Comput.
Sci., vol. 1, 1995, pp. 535–556], and Romaguera and Schellekens [S. Romaguera, M. Schellekens,
Quasi-metric properties of complexity spaces, Topology Appl. 98 (1999) 311–322]
introduced a topological foundation to obtain complexity results through the application
of Semantic techniques to Divide and Conquer Algorithms. This involved the fact that the
complexity (quasi-metric) space is Smyth complete and the use of a version of the Banach
fixed point theorem and improver functionals. To further bridge the gap between Semantics
and Complexity, we show here that these techniques of analysis, based on the theory of
complexity spaces, extend to General Probabilistic Divide and Conquer schema discussed by
Flajolet [P. Flajolet, Analytic analysis of algorithms, in: W. Kuich (Ed.), 19th Internat. Colloq.
ICALP’92, Vienna, July 1992; Automata, Languages and Programming, in: Lecture Notes in
Comput. Sci., vol. 623, 1992, pp. 186–210]. In particular, we obtain a general method which
is useful to show that for several recurrence equations based on the recursive structure
of General Probabilistic Divide and Conquer Algorithms, the associated functionals have a
unique fixed point which is the solution for the corresponding recurrence equation
