# zbMATH — the first resource for mathematics

Using fractal geometry for solving divide-and-conquer recurrences. (English) Zbl 0852.68101
Summary: 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 $$\Theta (n^D)$$, else it implies that the time complexity is of the form $$\Theta (n^D \log^pn)$$, where $$p$$ is an easily determined constant.

##### MSC:
 68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
fractal image
Full Text: