<p>The answer is no, there is no exponential bound on PR.
PR contains <a href="https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation">Knuth's up-arrow functions</a>, <a href="https://en.wikipedia.org/wiki/ELEMENTARY">Elementary functions</a>, etc.
PR is equal to the union of <a href="https://en.wikipedia.org/wiki/Grzegorczyk_hierarchy">Grzegorczyk hierarchy</a>.
Exponential functions appear at the third level of the Grzegorczyk hierarchy.</p>

<p>PR can alternatively be defined using the iteration function in place of recursion.</p>

<p>A good reference for information about these classes is the first chapter of second volume of "<a href="https://books.google.ca/books?id=Z97uAAAAMAAJ">Classical Recursion Theory</a>".</p>

<p>Also have the general function growth hierarchies like 
<a href="https://en.wikipedia.org/wiki/Grzegorczyk_hierarchy">Grzegorczyk hierarchy</a>,
<a href="https://en.wikipedia.org/wiki/Slow-growing_hierarchy">slow-growing hierarchy</a>, and
<a href="https://en.wikipedia.org/wiki/Fast-growing_hierarchy">fast-growing hierarchy</a>.</p>

CC BY-SA 3.0
2016-02-06T03:45:31.863Z
2016-02-06T04:03:51.250Z
2016-02-06T04:03:51.250Z
Kaveh
<p>Pardon me for asking a question whose answer is surely well-known, but
is beyond my expertise:</p>

<blockquote>
  <p><strong><em>Q</em></strong>. Is the growth rate of each <a href="https://en.wikipedia.org/wiki/Primitive_recursive_function">primitive recursive function</a> $f(n)$ bounded by some exponential $O(c^n)$, or $O(n^n)$, or ...?</p>
</blockquote>

<p>I know <a href="https://en.wikipedia.org/wiki/Ackermann_function">Ackermann's function</a> grows faster than exponential, but it is not primitive recursive.</p>

CC BY-SA 3.0
2016-02-06T03:30:47.320Z
I am also not an expert but I am pretty sure that towers of exponents, and maybe even $2\uparrow^k n$ for any constant $k$ are primitive recursive https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation.
Sasho Nikolov
CC BY-SA 3.0
2016-02-06T03:37:05.853Z
Actually, after googling something on a hunch, it [seems](https://books.google.ca/books?id=hsxDiWvVdBcC&lpg=PA332&pg=PA332#v=onepage&q&f=false) that for every primitive recursive function $f(n)$ there exists a constant $k$ such that $f(n) \le A(n,k)$, where $A$ the Ackermann function.
Sasho Nikolov
<recursion><recursive>
Growth rate of primitive recursive functions
Joseph O'Rourke
# Growth rate of primitive recursive functions

(Asked by: username_0 on 2016-02-06)

Pardon me for asking a question whose answer is surely well-known, but
is beyond my expertise:

> ***Q***. Is the growth rate of each [primitive recursive function](https://en.wikipedia.org/wiki/Primitive_recursive_function) $f(n)$ bounded by some exponential $O(c^n)$, or $O(n^n)$, or ...?

I know [Ackermann's function](https://en.wikipedia.org/wiki/Ackermann_function) grows faster than exponential, but it is not primitive recursive.

**Tags:** recursion, recursive

> **Comments:**
> **username_1**: I am also not an expert but I am pretty sure that towers of exponents, and maybe even $2\uparrow^k n$ for any constant $k$ are primitive recursive https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation.  
> **username_1**: Actually, after googling something on a hunch, it [seems](https://books.google.ca/books?id=hsxDiWvVdBcC&lpg=PA332&pg=PA332#v=onepage&q&f=false) that for every primitive recursive function $f(n)$ there exists a constant $k$ such that $f(n) \le A(n,k)$, where $A$ the Ackermann function.  

---

## 1 answers

### Answer by username_2 on 2016-02-06. Score: 12 | Accepted answer

The answer is no, there is no exponential bound on PR.
PR contains [Knuth's up-arrow functions](https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation), [Elementary functions](https://en.wikipedia.org/wiki/ELEMENTARY), etc.
PR is equal to the union of [Grzegorczyk hierarchy](https://en.wikipedia.org/wiki/Grzegorczyk_hierarchy).
Exponential functions appear at the third level of the Grzegorczyk hierarchy.

PR can alternatively be defined using the iteration function in place of recursion.

A good reference for information about these classes is the first chapter of second volume of "[Classical Recursion Theory](https://books.google.ca/books?id=Z97uAAAAMAAJ)".

Also have the general function growth hierarchies like
[Grzegorczyk hierarchy](https://en.wikipedia.org/wiki/Grzegorczyk_hierarchy),
[slow-growing hierarchy](https://en.wikipedia.org/wiki/Slow-growing_hierarchy), and
[fast-growing hierarchy](https://en.wikipedia.org/wiki/Fast-growing_hierarchy).


---

