There are two questions:
Define the set $S$. Compute the limit of functions $f/g$ for functions $f,g\in S$, where $S$ is defined in the following way.
All constant function are in $S$, $f(n) = n\in S$. Let $f,g\in S$.
- $f+g, f*g, f/g, f-g \in S$
- $f^g, \log_g(f) \in S$
- $f(g) \in S$
The limits are always of the form $\lim_{n\to \infty} f/g$.
What are some algorithms for this?If we introduce more functions in $S$, what do we know about computing the limit? Assume all functions are strictly increasing smooth functions. Is it computable?
I want this because there are times where one want to figure out how does the asymptotic running time of two algorithms compare to each other. It is easy when there are two algorithms with running time are $O(n)$ and $O(n^2)$, but it becomes hard when there are more things going on, for example, $O(\log n\log \log n)$ vs $O(e^{\sqrt{\log n}})$.
This algorithm would also allow one to simplify things in the big-$O$ notation. One can run the algorithm on $n^2 + n +\log n$ and figure out the $n^2$ is the dominating term.
I know I could just use Mathematica, but I would like to know how this is done. A paper would be helpful.
Per Chao Xu's request:
Dominik Gruntz's dissertation notes that the problem of taking limits can be shown to be equivalent to the zero-recognition problem, which is in general undecidable. In fact, the method given in Gruntz's dissertation has to assume the existence of an oracle to say which expressions are equivalent to work.