8

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

}
Thorben
  • 953
  • 13
  • 28
  • 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 http://oeis.org/A074877 – Dogbert Nov 11 '13 at 09:49

4 Answers4

4

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.

ARi
  • 141
  • 5
  • 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. – ARi Nov 03 '15 at 14:35
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

Chevy787
  • 45
  • 1
  • 5
  • Okay. So what's the name for it? Is the complexity class = PSEUDOPOLYNOMIAL? – Thorben Jun 28 '13 at 14:57
  • I'd say that's the complexity class. Also look @ http://arstechnica.com/civis/viewtopic.php?f=20&t=865597 – Chevy787 Jun 28 '13 at 15:21
  • Sounds good. Nevertheless I have read a little bit about ELEMENTARY http://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? – Thorben Jun 28 '13 at 15:33
  • I'm honestly unsure, but I'd say it's plausible. Hopefully someone else can clarify things. – Chevy787 Jun 28 '13 at 16:06
  • Okay, thanks. Until then I decided to classify it simply as non simple recursive, like it's purpose was. – Thorben Jun 28 '13 at 17:12
  • 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. – D.F.F Sep 23 '14 at 17:24
2

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

SomeWittyUsername
  • 18,025
  • 3
  • 42
  • 85
  • That's right, but I use it as a benchmark, so I took the Standardform from Péter. I Added a code example. – Thorben Jun 29 '13 at 11:25
2

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 ...

sosostris
  • 73
  • 8