0
$\begingroup$

I heard a statement saying that iterated logarithm and inverse Ackermann function are usually the slowest growing functions used in computer program complexity analysis. Is that true? What kind of computations or algorithms naturally give rise -- in the sense as does divide-and-conquer gives rise to logarithm -- to iterated logarithm and inverse Ackermann function?

$\endgroup$
3
  • 6
    $\begingroup$ It may help to study the classical data structure for the Union Find problem that uses union by rank and path compression. It's the earliest and maybe simplest example of inverse Ackermann growth. See Tim Roughgarden's lectures: class.coursera.org/algo2-2012-001/lecture/preview $\endgroup$ – Sasho Nikolov Mar 8 '14 at 22:06
  • 2
    $\begingroup$ One interpretation of iterated log/inverse Ackermann is that you can repeatedly do "divide and conquer" to get the bound. This comes from a nice proof of the union-find bound by Seidel and Sharir. $\endgroup$ – Suresh Venkat Mar 9 '14 at 4:55
  • $\begingroup$ @Sasho I've studied that as well as Sedgewick's version of find-union. But I still feel needing some high-level distillation of the problem. So if one can do divide and conquer and use divide-and-conquer iteratively for subproblems recursively, iterated logarithm and inverse Ackermann function arise? I feel this statement is kind of fuzzy. Could there be a proof to that without relying on the specifics of find-union problem? $\endgroup$ – qazwsx Mar 17 '14 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.