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

}

Mintun

The number of recursive calls that will be made for ack(3, n) using your code is exponential - you can calculate the exact number of calls it'll make from oeis.org/A074877 – Sonjasonnet

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.

Jemine

Ackermann function can not be programmed through a for next loop with the loop limit being any primitive recursive function of the argument. You will have to stick with the while loop with no idea about the number of iterations. – Jemine

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

Cusp

Okay. So what's the name for it? Is the complexity class = PSEUDOPOLYNOMIAL? – Mintun

I'd say that's the complexity class. Also look @ arstechnica.com/civis/viewtopic.php?f=20&t=865597 – Cusp

Sounds good. Nevertheless I have read a little bit about ELEMENTARY en.wikipedia.org/wiki/ELEMENTARY and I think the complement of it (NONELEMENTARY) would also describe the characeristics of this function. Would you say this is correct? – Mintun

I'm honestly unsure, but I'd say it's plausible. Hopefully someone else can clarify things. – Cusp

Okay, thanks. Until then I decided to classify it simply as non simple recursive, like it's purpose was. – Mintun

First pseudo-polinomial afaik means that the runtime of an algorithm is polynomial in the VALUE of the imput (instead of its length). Thus the definition given is wrong. As for the Ackermann function, afaik it is much much ... worse than polynomial or pseudo-polynomial! Even if the result could be computed immediately, since the resulting number is that large for even relatively small imputs, it would still take much more than whatever reasonable complexity class to just write down the result in binary. – Liatrice

Answer 3

If all you're interested in is Ack(3,n), it's O(exponentiation). Ack(3,n) = 2ⁿ⁺³-3. This can be computed with O(logn) operations.

Fant

That's right, but I use it as a benchmark, so I took the Standardform from Péter. I Added a code example. – Mintun

Answer 4

It's mostly the 3rd case that involves massive complexity... and it is in the form of (((2^2)^2)^2)^2 and so on... so, by inspection you can see that the complexity is 2^(2^n) ... this complexity is much worse than n^n, so i read somewhere else that ackermann's function is like the upper bound for primitive recursive functions but i'm not entirely sure about that ... need to do more research ...

Chatterbox