Time Complexity of ackermann function

Question

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

}

Answer 1

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.

Answer 2

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