Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Added

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.

share|improve this question
    
What would an absolute measure of growth even mean? All growth is relative. –  Qiaochu Yuan May 30 '11 at 13:36
    
@rank: Why should "linear," "polynomial," "exponential" not be thought of as absolute rates of growth? –  André Nicolas May 30 '11 at 13:54
    
This question is ill-posed: what is your idea of absolute growth? –  Glen Wheeler May 30 '11 at 15:07
1  
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$. –  Yuval Filmus May 30 '11 at 15:10
1  
The derivative? –  Alexei Averchenko May 30 '11 at 15:15
show 1 more comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
These look interesting, thank you for the pointers. –  rank May 30 '11 at 15:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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