The best known non-primitive recursive function is Ackermann's function which grows at rate f_ω in the Fast Growing Hierarchy [1]. Any computable function whos

The best known non-primitive recursive function is Ackermann's function which grows at rate f_ω in the Fast Growing Hierarchy [1]. Any computable function whose running time grows slower than that, i.e. bounded by some f_k for finite k, should be primitive recursive, since one can just add f_k(n) upper bounds to any unbounded loop without affecting the result. I think functions growing as fast as Ackermann's don't come up naturally, except on a Googology forum. > 6) QUESTION: We know that GO and CHESS have very high complexity, but are still prim recursive. > 7) Tarjan's UNION-FIND data structure has amortized complexity roughly O(n alpha(n)) where alpha(n) is the inverse of Ackermann's function. This is also a lower bound. See Wikipedia entry on disjoint-set data structure. QUESTION: Is Tarjan's UNION-FIND data structure actually used? I've used the union-find data structure for keeping track of groups of connected stones in Go. And also for keeping track of connected cells for generating random mazes. [1] https://en.wikipedia.org/wiki/Fast-growing_hierarchy https://en.wikipedia.org/wiki/Fast-growing_hierarchy