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.com Feb 23 '14 at 17:37

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

  • $\begingroup$ Is $n$ positive integer? what's the initial condition? Is this some sort of asymptotic time complexity problem? $\endgroup$ – Memming Feb 11 '14 at 11:55
  • $\begingroup$ @Memming Added a $\Theta(n)$ term, does this help answer your question? Yes, it is a asymptotic time complexity problem. $\endgroup$ – 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}). $$


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.