Which functions have growth rates between $\log n$ and $n$?

3.6k Views Asked by At

Is there any function with a rate of growth between $n$ and $\log(n)$?

My problem is that I have a value $x$, against which a term varies. The term does not vary as rapidly a linear function of $x$ but not as slowly as $log(x)$ (Choosing a different base of log can't help as for larger n the change in the function will still only happen for an large (exponential) increase).

How to model that function $f(x)$?

3

There are 3 best solutions below

1
On BEST ANSWER

$\log{n}$ grows more slowly than any positive power of $n$, so $n^{1/2}$, $n^{2/3}$, $n^{1/\pi}$ are all possibilities. You really need a more concrete idea of the growth to work out which applies.

1
On

The function $(\log n)^{\alpha}$ satisfies $$\lim_{n \to \infty} \frac{\log n}{(\log n)^{\alpha}} = 0 \qquad \textrm{and} \qquad \lim_{n \to \infty} \frac{(\log n)^{\alpha}}{n} = 0$$ for $\alpha > 1$. (Showing the first limit is straightforward---for the second, just apply L'Hôpital's Rule once.)

0
On

The function which gives the $x$-th Harmonic Number, $H_x = \sum_{n=1}^x \frac{1}{n}$ approaches $\ln x + \gamma$ for very large $x$, where $\gamma$ is the Euler-Mascheroni constant, ~$.577...$. No rational function is asymptotic to $\ln x$ because all rational functions are asymptotix to $x^k$ for some integer $k$, is that what you're after? If you just want a function that grows less than $y=x$ but more than $\ln x$, this would be satisfied by $y=x^{1/n}$ for any $n \gt 1$.