How to solve recurrences involving log?

For example,

$T(n) = \log {n} \cdot T(\frac{n}{\log{n}}) + \Theta(n)$

I tried using the substitution method with $n = 2^m$, but that got me nowhere, since it still ends up with a $m$ and $2^m$. The recurrence tree method also becomes rather complicated. Is there a general approach to follow to solve such recurrences?

migrated from math.stackexchange.comFeb 23 '14 at 17:37

This question came from our site for people studying math at any level and professionals in related fields.

• Is $n$ positive integer? what's the initial condition? Is this some sort of asymptotic time complexity problem? – Memming Feb 11 '14 at 11:55
• @Memming Added a $\Theta(n)$ term, does this help answer your question? Yes, it is a asymptotic time complexity problem. – Happy Feb 11 '14 at 11:57

Define a sequence $n_0 = n$, $n_{t+1} = n_t/\log n_t$. Assuming that the underlying constant in $\Theta(n)$ is $1$, we get \begin{align*} T(n) &= \log n_0 T(\tfrac{n_0}{\log n_0}) + n_0 \\ &= \log n_0 \log n_1 T(\tfrac{n_1}{\log n_1}) + n_0 + n_1 \log n_0 \\ &= \log n_0 \log n_1 \log n_2 T(\tfrac{n_2}{\log n_2}) + n_0 + n_1 \log n_0 + n_2 \log n_1 \log n_0 \\ &= \cdots \end{align*} Now $n_{t+1} \log n_t = n_t$, and so $n_1\log n_0 = n_0$, $n_2\log n_1\log n_0 = n_1\log n_0 = n_0$, and so on.
Suppose now that the starting condition of your recurrence is $T(x) = 1$ for $x \leq 1$, and let $\ell+1$ be the minimal index such that $n_{\ell+1} \leq 1$. Then $$T(n) = \log n_0 \log n_1 \cdots \log n_\ell + (\ell + 1) n.$$ In fact, $\log n_0\cdots n_\ell n_{\ell+1} = n$, and clearly $n_{\ell+1} = \Omega(1)$, showing that $T(n) = (\ell + O(1))n$.
It remains to estimate $\ell$. Clearly $n_t \geq n/\log^t n$, and so $\ell \geq \log n/\log\log n$. For the other direction, notice that when $t \leq \log n/2\log\log n$, we have $n_t \geq \sqrt{n}$, and so $n_t \leq n/(\log n/2)^t$. This shows that $n_{\log n/2\log\log n} \leq \sqrt{n} 2^{\log n/2\log\log n} \leq n^{0.51}$ for $n$ larger than some constant $C$. Repeating the same argument, $n_{\log n/2\log\log n + \log n^{0.51}/2\log\log n^{0.51}} \leq n^{0.51^2}$ for $n^{0.51} \geq C$. Notice that $\log n^{0.51}/2\log\log n^{0.51} \leq 0.52\log n/2\log\log n$, for $n$ larger than some constant $C'$. Repeating this argument $k = O(\log\log n)$ times, we get that for $t = \log n/(2\log\log n) (1 + 0.52 + 0.52^2 + \dots) = O(\log n/\log\log n)$ we have $n_t = n^{0.51^k} = O(1)$. This shows that $\ell = \Theta(\log n/\log \log n)$, and so $$T(n) = \Theta(n\tfrac{\log n}{\log\log n}).$$