Editing Ackermann function (section)

== Inverse ==
Since the function {{nowrap|1=''f''(''n'') = ''A''(''n'', ''n'')}} considered above grows very rapidly, its [[inverse function]], ''f''{{i sup|−1}}, grows very slowly. This '''inverse Ackermann function''' ''f''<sup>−1</sup> is usually denoted by '''''α'''''. In fact, ''α''(''n'') is less than 5 for any practical input size ''n'', since {{nowrap|''A''(4, 4)}} is on the order of <math>2^{2^{2^{2^{16}}}}</math>.

This inverse appears in the time complexity of some algorithms, such as the [[disjoint-set data structure]] and [[Bernard Chazelle|Chazelle]]'s algorithm for [[minimum spanning tree]]s. 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 <math>\lfloor x \rfloor</math> is the [[floor function]]:

<math display="block">\alpha(m,n) = \min\{i \geq 1 : A(i,\lfloor m/n \rfloor) \geq \log_2 n\}.</math>

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 {{nowrap|''α''(''m'', ''n'')}} exist; for example, {{nowrap|log<sub>2</sub> ''n''}} is sometimes replaced by ''n'', and the floor function is sometimes replaced by a [[ceiling function|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.{{sfn|Pettie|2002}}

The inverse of the Ackermann function is primitive recursive, since it is graph primitive recursive, and it is upper bounded by a primitive recursive function.{{sfn|Matos|2014}}