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?

  • 0
    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".2012-01-09
  • 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'2012-01-09
  • 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