In computer science there are many notions of growth-rate of a function. These notions are, however, always relative in the sense that growth-rate of some function $f$ is always relative to some other function $g$, i.e. bigger, equal or smaller.

Does there exists any absolute measure of growth-rage for, say, number-theoretical functions? For example $f$ has growth rate $n$ if this-and-that.


Seems the question is hard to understand or there is something I miss (likely the latter). I'm after a method to define the growth-rate of a function as a number $n\in\mathbb{N}$ instead of comparing the growth to another function. For example in the class of primitive recursive functions one could define $f\in PR$ a growth-rate as the level $i$ Grzegorczyk-hierarchy such that $f\in E_i$ but $f\notin E_{i-1}$.

I guess this reverts to hierarchies of (total) functions based on their growth-rate.

There is no deeper motivation behind, I just thought if there are some ways to define absolute growth-rate in the aforementioned sense.

  • $\begingroup$ What would an absolute measure of growth even mean? All growth is relative. $\endgroup$ – Qiaochu Yuan May 30 '11 at 13:36
  • $\begingroup$ @rank: Why should "linear," "polynomial," "exponential" not be thought of as absolute rates of growth? $\endgroup$ – André Nicolas May 30 '11 at 13:54
  • $\begingroup$ This question is ill-posed: what is your idea of absolute growth? $\endgroup$ – Glen Wheeler May 30 '11 at 15:07
  • 1
    $\begingroup$ I also don't agree with your interpretation of "order of growth" as relative. A function $f$ has order of growth $g$ if $f = \Theta(g)$. There's nothing relative here. For example, $n!$ has order of growth $\sqrt{n} (n/e)^n$. $\endgroup$ – Yuval Filmus May 30 '11 at 15:10
  • 1
    $\begingroup$ The derivative? $\endgroup$ – Alexei Averchenko May 30 '11 at 15:15

You may be interested in fast-growing hierarchies, although, reiterating the comments, $f = \Theta(g)$ is the same as saying that $f$ grows like $g$.

You could also check out Hardy's classic Orders of infinity.

One more thing to mention is the circle of ideas around Cichon's diagram. You can define an "order of growth" as an increasing function from naturals to naturals. An order of growth $\alpha_i$ is greater (grows faster) than an order of growth $\beta_i$ if $\alpha_i/\beta_i \rightarrow \infty$ (there are other definitions possible). Is there a "scale" of orders, i.e. a well-ordered set of orders of growth which is cofinal (for each order of growth, it contains a greater one)? That's independent of ZFC.


Your Answer

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