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.

Is there any simple function/formula $f(n)$, which eventually dominates every $cn$ for every $c$, and is eventually dominated by $a \cdot n \cdot \ln^k(n)$ for every $a,k \in \mathbb{Z}$, where $\ln^k(n)=\ln(\ln^{k-1}(n))$, $\ln^1(n)=\ln(n)$. Edit: And which is not defined in terms of ln(n) (end edit)

And is there any natural/simple formulas or system which obeys growth rates not expressible by the familiar $x^r, \ln(x), e^x$... ? Why does this finite set seem to generate all natural growth rates, like the prime-numbers $\rightarrow n\ln n$, and factorial$\rightarrow n!\rightarrow e^n$

Has the countable collection of all nondecreasing computable functions under the equivalence relation of $\lim f\cdot g^{-1} = \text{ constant}$, and the ordering of eventual domination been studied?

Where can I read about this?

share|improve this question
    
What would you consider "natural" or "simple"? First of all, there are trigonometric functions which certainly appear. Regarding your last item, of course they have. Search for "asymptotic analysis". –  Raphael Jan 9 '12 at 11:57
1  
Raphael, something which isnt artificially constructed in terms of the lower and upper bounding functions through some limiting or averaging process, or 'picking a value inbetween for every x' –  jedi Jan 9 '12 at 15:25
1  
Note that the order of the factorial is greater than that of $e^x$ or $b^x$ for any constant b. –  Charles Jan 9 '12 at 21:29

3 Answers 3

Since the question has been changed to disallow functions based on the logarithm (for some reasn), I suggest $n\alpha(n)$ is an example, where $\alpha(n)$ is the inverse Ackermann function. This arises (among other places) in the analysis of a minimum spanning tree algorithm, see Chazelle 2000.

share|improve this answer

I'm not entirely sure how best to specify precisely the requirement that the answer should avoid the logarithm. I do have such a specification in mind, but instead I will state, and then solve, a similar but simpler question, so that I can then make a comment about how to adapt the answer to "solve" your question, modulo the logarithm-avoiding requirement. You can judge for yourself whether this will help you in any way. And yes, the "ordering" of the asymptotic behaviour of real-valued functions involving exponential and logarithmic functions and their compositions have been studied, according to a faint memory I have of reading a particular paper in the past. I suggest that you investigate objects called Hardy fields and valuations on such fields. The valuation essentially "grades" how fast each element of the field grows, and two functions $f$, $g$ having the same valuation essentially means $\lim_{x\to\infty} \frac{f(x)}{g(x)} = C$ for some constant $C \in \mathbb{R}$. I would visit the Wikipedia article on Hardy fields first, and sort of skim the last reference listed.

Without further ado, suppose I have a sequence of functions $f_1, f_2, \ldots$ such that $f_n \in o(f_{n+1})$ for all $n \geq 1$. Does there exist a function $F$ such that $f_n \in o(F)$ for all $n$? The answer is yes. We simply construct $F(x)$ starting at $x = 0$ by first behaving like $f_1$ for at least the interval $[0, 1]$, until $f_2$ exceeds $f_1$, at which point $F$ will switch to behave like $f_2$, until the point where $f_3$ exceeds $f_2$ (or until $x = 2$, whichever comes later), and so on. Now of course any function in the sequence will grow slower than this "pieced together" $F$. To adapt this to your question, we simply piece together sections from $\ln^k$ in this fashion (so that it grows ever slower; edit: some details are missing here), and multiply that by the identity function $x$.

I will state a possible way to formulate your requirement that the solution "avoid the logarithm". Consider the smallest function field (of germs at $\infty$; please read the Hardy field Wikipedia article) containing $x$, $\mathbb{R}$ (the constant functions), and $\ln(x)$, and is closed under composition. Then the requirement is simply to avoid functions in this field.

I think what I said above can contain errors...I haven't rigorously proven anything on paper yet, but I am fairly certain those work. But in any case I still hope this post will be helpful to you.

share|improve this answer
    
That formulation still allows log*, which I think is contrary to the intent of the question. (Perhaps 0.999 will comment?) –  Charles Jan 16 '12 at 1:40
    
Also, I think your pieced-together function F is bounded above, so that it does not dominate cn. –  Charles Jan 16 '12 at 22:34

A popular example for your first question is $n\cdot\ln^*(n)$ with $\ln^*(n)$ being the biggest integer $k$ such that $\ln^k(n) > 0$. It arises during the analysis of a solution of UNION-FIND using binary search trees with path-compression.

share|improve this answer
1  
Are you sure? It seems $\ln^n(x)$ is defined only for $x\gt x_n$ with $x_1=0$ and $x_{n+1}=\mathrm e^{x_{n}}$ for every $n\geqslant1$. Hence $x_n\gt n$ for every $n\geqslant4$ and I wonder how $\ln^n(n)$ is defined. –  Did Jan 9 '12 at 13:37
    
The comment above applies to a previous version of Raphael's answer. User @Lierre now modified the definition of the function $\ln^*$. –  Did Jan 9 '12 at 16:10
    
True comment; thanks for the edit, @Lierre. –  Raphael Jan 13 '12 at 22:08

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.