J Austral Math Soc Ser B 37 pp145--171, 1995.

Using fractal geometry for solving divide-and-conquer recurrences

Simant Dube

Abstract

A relationship between the fractal geometry and the analysis of recursive (divide-and-conquer) algorithms is investigated. It is shown that the dynamic structure of a recursive algorithm which might call other algorithms in a mutually recursive fashion can be geometrically captured as a fractal (self-similar) image. This fractal image is defined as the attractor of a mutually recursive function system. It then turns out that the Hausdorff-Besicovich dimension D of such an image is precisely the exponent in the time complexity of the algorithm being modelled. That is, if the Hausdorff D-dimensional measure of the image is finite then it serves as the constant of proportionality and the time complexity is of the form Q(n^D ), else it implies that the time complexity is of the form Q(n^D log ^pn), where p is an easily determined constant.

Browse the article

Author

Simant Dube

Iterated Systems Inc., Seven Piedmont Centre, Atlanta GA 30305, USA.