3
$\begingroup$

How would one go about classifying the time complexity of Ackermann's function, and can we say that all primitive-recursive functions are asymptotically bounded by the complexity of the Ackermann function as an asymptotic upper bound?

Edit: I want to make it clear that I am interested in the time complexity of computing Ackermman's function and whether the time complexity of computing any primitive recursive function is asymptotically bounded by the time complexity of computing Ackermman's function. I am not interested in the actual values of those functions.

I am asking because I remember seeing an assertion of my second question in an old book but no proof was shown and no time complexity for computing Ackermman's function was listed, so the assertion was by no means rigorous.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Complexity in what sense? Time complexity? Space complexity? Please define your terms, or explain what you mean by them. What do you mean when you say that a class of functions is "bounded by" something, or "bounded by the complexity of something"? Please elaborate in the question and explain the concepts you have in mind. I suspect you might have some misunderstandings of the meanings of some of those terms, but since your question is so terse it's hard to tell for sure. See also cs.stackexchange.com/q/13669/755, including the explanations about the use of the term "complexity". $\endgroup$ – D.W.♦ Sep 16 '15 at 0:54
  • $\begingroup$ Time complexity. I would like to know how to classify the time complexity of the ackermann function and whether we can say the time complexity of the ackermann function is an asymptotic upper bound for all for all primitive recursive functions. $\endgroup$ – Francesco Gramano Sep 16 '15 at 0:59
  • $\begingroup$ Please edit the question to add all relevant clarifications and improve it to be a coherent, well-fleshed-out question. Don't just drop clarifications in the comments: questions should stand on their own, and people should be able to understand the question without reading the comments. (Also: What are your thoughts? What research/self-study have you done?) $\endgroup$ – D.W.♦ Sep 16 '15 at 1:00
  • $\begingroup$ Is it clear what I am asking now? I had tried to revisit old books on complexity theory but none which seem to mention the time complexity of Ackermann's function, just that it is total, strictly recursive and not primitive recursive. $\endgroup$ – Francesco Gramano Sep 16 '15 at 1:04
6
$\begingroup$

You are asking (or at least typing) multiple questions that are unrelated.

Time Complexity of the Ackermann function

First, understand that this is not a meaningful query. The Ackermann function, let's call it $A$ (assume a one-parameter variant), is a function, not an algorithm. You can certainly talk about $\Theta(A)$.

What you likely mean is the time $T_A(n)$ required to compute $A(n)$. I do not know of any algorithm besides explicitly computing the recurrence; the runtime of this approach can be investigated using the standard approach. It's unlikely that the result will be a meaningful $\Theta$-asymptotic in terms of the "usual" basic functions; you'd get runtime bounds expressed in $A$ itself.

That does not mean that there is no faster algorithm; it would not contradict the growth of $A(n)$ per se. Depending on your computational and cost model, you can compute huge numbers with little cost.

Are all primitive-recursive functions in $O(A)$?

Yes. That is (a consequence of) how we show that $A$ is not primitive recursive.

Note that here we are back to comparing values of the functions again; no mention of "time complexity" is being made.

Can all primitive-recursive functions be computed in time $O(T_A(n))$?

Not knowing $\Theta(T_A)$, I do not have an answer to this question.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This doesn't really answer my question. My initial question was pretty vague, granted, but I've edited it to reflect the more meaningful question for which I was searching for an answer. $\endgroup$ – Francesco Gramano Sep 17 '15 at 18:21
1
$\begingroup$

On the phone, so forgive brevity, however, I think you're looking for the concept of tetration and the arrow notation.

With those concepts in hand, I think runtime complexity of Ackermann function ($A~a~b$), as defined in Structure and Interpretation of Computer Programs book, has the time complexity of $O (n (↑))$ where $n(↑)$ means $n$ number of arrows and $n = a - 2$. $(A~1~x)$ will take $x$ steps. $(A~2~x)$ will take $2x$ steps, $(A~3~x)$ will take $2↑x$ or $2^x$ steps. $(A~4~x)$ will take $2↑↑x$ steps, and so on.

I'm not certain this is exactly right, but this is the neighborhood. I'm just wrapping my head arround arrow notation in this context.

So, regarding whether Ackermann function (as implemented in SICP) can be used as an upper bound on some other algorithm, I think can be reduced to the question if primitive recursive algorithms are upper bounded by $O(n(↑))$

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.