Since the function considered above grows very rapidly, its inverse function, f, grows very slowly. This inverse Ackermann function f−1 is usually denoted by α. In fact, α(n) is less than 5 for any practical input size n, since is on the order of . This inverse appears in the time complexity of some algorithms, such as the disjoint-set data structure and Chazelle's algorithm for minimum spanning trees. Sometimes Ackermann's original function or other variations are used in these settings, but they all grow at similarly high rates. In particular, some modified functions simplify the expression by eliminating the −3 and similar terms. A two-parameter variation of the inverse Ackermann function can be defined as follows, where is the floor function: This function arises in more precise analyses of the algorithms mentioned above, and gives a more refined time bound. In the disjoint-set data structure, m represents the number of operations while n represents the number of elements; in the minimum spanning tree algorithm, m represents the number of edges while n represents the number of vertices. Several slightly different definitions of exist; for example, is sometimes replaced by n, and the floor function is sometimes replaced by a ceiling. Other studies might define an inverse function of one where m is set to a constant, such that the inverse applies to a particular row. The inverse of the Ackermann function is primitive recursive. Use as benchmark The Ackermann function, due to its definition in terms of extremely deep recursion, can be used as a benchmark of a compiler's ability to optimize recursion. The first published use of Ackermann's function in this way was in 1970 by Dragoș Vaida and, almost simultaneously, in 1971, by Yngve Sundblad. Sundblad's seminal paper was taken up by Brian Wichmann (co-author of the Whetstone benchmark) in a trilogy of papers written between 1975 and 1982. See also Computability theory Double recursion Fast-growing hierarchy Goodstein function Primitive recursive function Recursion (computer science) Notes References Bibliography External links An animated Ackermann function calculator Ackerman function implemented using a for loop Scott Aaronson, Who can name the biggest number? (1999) Ackermann functions. Includes a table of some values. Hyper-operations: Ackermann's Function and New Arithmetical Operation Robert Munafo's Large Numbers describes several variations on the definition of A. Gabriel Nivasch, Inverse Ackermann without pain on the inverse Ackermann function. Raimund Seidel, Understanding the inverse Ackermann function (PDF presentation).