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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to solve the following functional equation using any ways:

$$T(n)=(\log n)T(\log n)+n$$

share|cite|improve this question
Perhaps you should replace $T(\log n)$ with $T(\lceil \log n \rceil)$, as otherwise you're going to need a lot of initial values for $T$. – Alex Becker Feb 25 '13 at 21:47

These kind of equations usually appear in analysis of the complexity of algorithms. The symbol $T$ stands for "time" in these cases. If your question is related to this field, it's often sufficient to find out the asymptotic behaviour of the function $T$. For example, in this particular case, you can show that for large enough $n$, $$n\leq T(n)\leq n+c\cdot(\log n)^{\log^*n}$$ where $c$ is a constant and $log^*$ denotes the iterated logarithm function. The proof is a simple inductive one: $$T(n)=(\log n)T(\log n)+n\\ \leq n+(\log n)\left(\log n+c\cdot(\log\log n)^{\log^*\log n}\right)\\ \leq n+c\cdot(\log n)^{\log^*n}$$ The second inequality above is valid for large enough $n$. So $c$ may be chosen in a way that the inequalities hold for that $n$ and by the inductive step, we'll get what we wanted to prove.
Now,because we have $$\lim_{n\to\infty}\frac{(\log n)^{\log^*n}}{n}= \lim_{n\to\infty}e^{(\log\log n)\log^*n-\log n} =\lim_{x\to-\infty}e^x=0$$ therefore $T(n)=\Theta(n)$ in which $\Theta$ stands for big theta notation. Hope it helps.

share|cite|improve this answer

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.