<p>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? </p>

CC BY-SA 3.0
2014-03-08T22:06:03.993Z
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: https://class.coursera.org/algo2-2012-001/lecture/preview
Sasho Nikolov
CC BY-SA 3.0
2014-03-09T04:55:17.743Z
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.
Suresh Venkat
CC BY-SA 3.0
2014-03-17T22:37:04.780Z
@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?
qazwsx
<complexity-classes>
What kind of computations or algorithms give rise to iterated logarithm and inverse Ackermann function?
qazwsx
# What kind of computations or algorithms give rise to iterated logarithm and inverse Ackermann function?

(Asked by: username_0 on 2014-03-08)

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?

**Tags:** complexity-classes
> **Comments:**
> **username_1**: 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: https://class.coursera.org/algo2-2012-001/lecture/preview  
> **username_2**: 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.  
> **username_0**: @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?  

---

## 0 answers

