# concerning growth rate of functions

I'm not sure how to state my question precisely. What I have in mind is roughly as follows: Are the exponential functions the slowest functions that grow faster than polynomials? In other words, I want to know if the gap between polynomials and exponential functions in terms of their growth is filled with any other type of functions.

The following is what is meant for $$f(x)$$ to grow faster than any polymonial:

$$\lim_{x\to \infty} \displaystyle\frac {f(x)}{P(x)}=\infty$$, for any polynomial $$P(x)$$.

I guess one way to state the the question is whether $$f(x)=f_1of_2o ... of_k(x)$$ where at least one of the $$f_i$$ is of the form $$a^x$$.

• Does $\dfrac{e^x}{x}$ count? Sep 24, 2018 at 18:27
• @user58697: that does not grow slower than $1.1^x$ for example Sep 24, 2018 at 18:28

## 1 Answer

The usual answer is that of course there are such functions. The challenge is to define them. It depends a bit on what you mean by exponential. If we define $$f(n)=2^{\sqrt n}$$ it grows faster than any polynomial and slower than $$a^n$$ for any $$a \gt 1$$. Given such an $$a$$ we have $$a^n=(a^{\sqrt n})^{\sqrt n}$$ so if we choose $$n$$ large enough that $$a^{\sqrt n} \gt 2$$ we have $$a^n \gt 2^{\sqrt n}$$

• "The usual answer is that of course there are such functions" Really? Read the question carefully, the function $2^{\sqrt{n}}$ that you are proposing is exactly of the expected form $f_1o...f_k$ where at least one $f_i$ is exponential. The question is to find a function that is not in this form. Sep 24, 2018 at 19:17
• @kaveka: Any function can be put in this form with $f_k=e^n, f_{k-1}=\log x$ so that is not a valid criterion. My function does not fit the usual definition of an exponential function because of the square root. Sep 24, 2018 at 19:20
• nice so earned more points but did not actually answer the question. Sep 24, 2018 at 23:13