Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-22T07:11:39.076Z Has data issue: false hasContentIssue false
  • English
  • Français

Using fractal geometry for solving divide-and-conquer recurrences

Published online by Cambridge University Press:  17 February 2009

Simant Dube
Simant Dube
Affiliation:
Iterated Systems Inc., Seven Piedmont Centre, Atlanta GA 30305, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 Θ(nD), else it implies that the time complexity is of the form Θ(nD logpn), where p is an easily determined constant.

Type
Research Article
Information
The ANZIAM Journal , Volume 37 , Issue 2 , October 1995 , pp. 145 - 171
Copyright
Copyright © Australian Mathematical Society 1995

References

[1]Aho, A. V., Hopcroft, J. E. and Ullman, J. D., The design and analysis of computer algorithms (Addison-Wesley, 1974).Google Scholar
[2]Barnsley, M. F., Fractals everywhere (Academic Press, 1988).Google Scholar
[3]Barnsley, M. F., Elton, J. H. and Hardin, D. P., “Recurrent iterated function systems”, Constructive Approximation 5 (1989) 3–31.CrossRefGoogle Scholar
[4]Barnsley, M. F., Devaney, R. L., Mandelbrot, B. B., Peitgen, H.-O., Saupe, De and Voss, R. F., Science of fractal images (Springer-Verlag, 1988).CrossRefGoogle Scholar
[5]Bentley, J. L., Haken, D. and Saxe, J. B., “A general method for solving divide-and-conquer recurrences”, SIGACT News 12 (1980) 36–44.CrossRefGoogle Scholar
[6]Cormen, T. H., Leiserson, C. E. and Rivest, R. L., Introduction to algorithms (MIT Press, 1990).Google Scholar
[7]Culik, K. II and Dube, S., “Affine automata and related techniques for generation of complex images”, Theoretical Computer Science 116 (1993) 373–398.CrossRefGoogle Scholar
[8]Culik, K. II and Dube, S., “Rational and affine expressions for image synthesis”, Discrete Applied Mathematics 41 (1993) 85–120.CrossRefGoogle Scholar
[9]Culik, K. II and Dube, S., “Balancing order and chaos in image generation”, Computer and Graphics 17 (4) (1993) 465–486.CrossRefGoogle Scholar
[10]Gantmacher, F. R., Applications of the theory of matrices (Interscience Publishers, 1959).Google Scholar
[11]Graham, R. L., Knuth, D. E. and Patashnik, O., Concrete mathematics (Addison-Wesley, 1989).Google Scholar
[12]Greene, D. H. and Knuth, D. E., Mathematics for the analysis of algorithms (Birkhäser, Boston, 1982).Google Scholar
[13]Hutchinson, J., “Fractals and self-similarity”, Indiana University J. of Mathematics 30 (1981) 713–747.CrossRefGoogle Scholar
[14]Mandelbrot, B., The fractal geometry of nature (W. H. Freeman and Co., San Francisco, 1982).Google Scholar
[15]Mauldin, R. D. and Williams, S. C., “Hausdorff dimension in graph directed constructions”, Trans. AMS 309 (1988) 811–829.CrossRefGoogle Scholar
[16]Purdom, P. W. Jr and Brown, C. A., The analysis of algorithms (Holt, Rinehart and Winston, 1985).Google Scholar
[17]Staiger, L., “Quadtrees and the Hausdorff dimension of pictures”, in Workshop on geometrical problems of image processing (GEOBILD'89), Math. Research No. 51, (Akademie-Verlag, Berlin, 1989), 173–178.Google Scholar