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.

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