0
$\begingroup$

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$.

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

1 Answer 1

1
$\begingroup$

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}$

$\endgroup$
3
  • $\begingroup$ "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. $\endgroup$
    – julesc
    Sep 24, 2018 at 19:17
  • $\begingroup$ @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. $\endgroup$ Sep 24, 2018 at 19:20
  • $\begingroup$ nice so earned more points but did not actually answer the question. $\endgroup$
    – julesc
    Sep 24, 2018 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.