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.

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

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

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

1 Answer 1

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 enouge $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 enouge $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|improve this answer

Your Answer

 
discard

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.