Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I learned something fascinating this week! (Unrelated to OP). The algebraic computation of the Hausdorff dimension of a fractal set is *exactly the same* as the Master Equation of the asymptotic analysis of algorithms! I.e.: where a Sierpinski triangle has dimension log(3)/log(2) ~ 1.58—intermediate in between that of a line and of a plane—that's the very same log(3)/log(2) as in the O(n^(log(3)/log(2)) of, say, the Karatsuba algorithm. In Karatsuba, when you recursively split a digit representation of a number in half (2), you get three new multiplications (3). In a Sierpinski triangle, rescaling by a factor of 2 increases the number of non-empty triangles at that scale by 3. And it really is the *same* manipulation: the Hausdorff dimension of the fractal is a critical exponent of an asymptotic function growth rate, a function of the diameters in a covering set in the ε→0 limit.

https://en.wikipedia.org/wiki/Hausdorff_dimension



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: