Eckerman function time complexity

Question

Does anyone know the time complexity for calculating the ackermann function ack (m, n) in Big-O notation, or to which complexity class does it belong? Just Ack (3, n) would also suffice. I read somewhere, it SHOULD NOT?

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)); } } 

Answer 1

Asymptotic worst case calculation time limits, expressed as a function of input length or time complexity: cannot be defined for mu-recursive functions, and not atlest without reference to another mu-recursive function, which is very different from a typical large notation. And this is only for those mu recursive functions that are "total", like our subject.

Answer 2

I don’t know too much about this function, but looking quickly at it, it seems pseudopolynomial. That is, the execution time depends on its input and may be polynomial time at certain inputs, and not a polynomial for others. This could be proved using Cantor's diagonalization.

Answer 3

If all that interests you is Ack (3, n), this is O (exponentiation). Ack (3, n) = 2 ^{n + 3} -3. This can be calculated using O (logn) operations.

Answer 4

This is basically the third case, which involves tremendous complexity ... and it is in the form (((2 ^ 2) ^ 2) ^ 2) ^ 2, etc .... therefore, that complexity is 2 ^ ( 2 ^ n) ... this complexity is much worse than n ^ n, so I read somewhere else that the ackermann function is like an upper bound for primitive recursive functions, but I'm not quite sure about this ... more research is needed ...