Using fractal geometry for solving divide-and-conquer recurrences. (English) Zbl 0852.68101

Dube, Simant

J. Aust. Math. Soc., Ser. B 37, No. 2, 145-171 (1995).

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)

Keywords:

fractal image