Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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