2
$\begingroup$

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?

  • 1
    Note that the order of the factorial is greater than that of $e^x$ or $b^x$ for any constant b.2012-01-09

3 Answers 3

2

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.

1

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.

  • 0
    Also, I think your pieced-together function F is bounded above, so that it does not dominate cn.2012-01-16
0

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.

  • 0
    True comment; thanks for the edit, @Lierre.2012-01-13