# How to solve the functional equation : $T(n)=(\log n)T(\log n)+n$

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

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

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