4
$\begingroup$

For analyzing the running time of an algorithm , I'm stuck with this recursive equation : $$ T(n) = \log(n) \cdot T(\log n) + n $$ Obviously this can't be handled with the use of the Master Theorem, so I was wondering if anybody has any ideas for solving this recursive equation.

I'm pretty sure that it should be solved with a change in the parameters, like considering $n$ to be $2^m$, but I couldn't manage to find any good fix.

$\endgroup$
1
5
$\begingroup$

I suppose you are looking for an asymptotic bound. Notice that the recursion depth is $\log^* n$, that is how often do I have to apply the logarithm recursively to get below 2. Also, the function is increasing. Using these two facts, you can plug in the recursion once and then you see that you have at most $\log^*$ summands, each of them at most $\log^2 n$ and then the additional $n$. This sum is dominated by $n$.

$$ \begin{align} T(n)&=\log(n) T(\log n)+n=\log n \log\log n \;T(\log\log n)+\log^2(n)+n \\ &\le \log^*n\log^2n+n=O(n) \end{align} $$

Clearly $T(n)\ge n$ and thus $T(n)=\Theta(n)$.

$\endgroup$
1
  • $\begingroup$ I have some remarks. 1. This recursive relation does not stop; then it is not defined.It is because sufficient base cases are not provided; for instance, use floor function and give $T(2)$ if $\log$ is the binary logarithm. Thus, I think that we should not accept this kind of presentation. 2. I read the Schulz's answer and I'm stumped. Firstly I do not understand the notation $\log^*$. Secondly is the proof by recurrence ? If yes, where is the hypothesis ? Moreover one must begin the recurrence. Then, if one wants to show $T(n)\leq cn$, then $c$ depends on the value chosen for $T(2)$. $\endgroup$ – loup blanc Oct 10 '13 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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