Menu
Does anybody know the time complexity to compute the ackermann function ack(m,n) in big-O notation or to which complexity class it belongs? Just Ack(3, n) would be also sufficient. I read somewhere it is NONELEMENTARY?
Thanks.
Code Snippet:
public class Ackermann {
public static int ackermann(int n, int m) {
if (n == 0)
return m + 1;
else if (m == 0)
return ackermann(n - 1, 1);
else
return ackermann(n - 1, ackermann(n, m - 1));
}
}
598
The Ackermann function is the simplest example of a well-defined total function which is computable but not primitive recursive, providing a counterexample to the belief in the early 1900s that every computable function was also primitive recursive (Dötzel 1991).
The inverse Ackermann function α(n) assigns to each integer n the smallest k for which α k(n) ≤ 3: α(n) = min { k : α k(n) ≤ 3 }. Thus, α(9876!) = 5.
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive.
(algorithm) Definition: A function of two parameters whose value grows very fast. Formal Definition: A(0, j)=j+1 for j ≥ 0.
Asymptotic limits of worst case computation time expressed as the function of input length or the time complexity : Can not be defined for mu recursive functions, not atlest without referring to another mu recursive function very different from the typical big oh notation. And this only for those mu recursive functions which are 'total' like our subject.
140
I don't know too much about this function, but quickly looking at it, it seems to be pseudo-polynomial. That is, the runtime depends on it's input and can be polynomial-time on certain inputs while non-polynomial on others. This could be proven using Cantor's Diagonalization
24
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
