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$$
 A: 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 behavior of the function $ T $. For example, in this particular case, you can show that for large enough $ n $,
$$ n \le T ( n ) \le n + c \cdot ( \log n ) ^ { \log ^ * n } \text , $$
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 \\
\le n + ( \log n ) \left( \log n + c \cdot ( \log \log n ) ^ { \log ^ * \log n } \right) \\
\le n + c \cdot ( \log n ) ^ { \log ^ * n } \text . $$
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 } \exp \big( ( \log \log n ) \log ^ * n - \log n \big) = \lim _ { x \to - \infty } \exp x = 0 $$
therefore $ T ( n ) = \Theta ( n ) $ in which $ \Theta $ stands for big theta notation.
Hope it helps.
