# Algorithm for finding limits of compositions of simple functions?

There are two questions:

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

1. $f+g, f*g, f/g, f-g \in S$
2. $f^g, \log_g(f) \in S$
3. $f(g) \in S$

The limits are always of the form $\lim_{n\to \infty} f/g$.
What are some algorithms for this?

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

-
I haven't read the whole thing, but could you check Dominik Gruntz's thesis and see if there's something you can use? – J. M. Sep 7 '11 at 2:33
Great! Section 3 answers the question. This is called the dominance problem. Unfortunately this problem is already undecidable given exponential and logarithms. Thanks. You can turn this to a answer. – Chao Xu Sep 7 '11 at 3:12