snippetMinor
How to solve recurrences involving log?
Viewed 0 times
recurrencesloginvolvingsolvehow
Problem
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?
$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?
Solution
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}). $$
$$
\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}). $$
Context
StackExchange Computer Science Q#21947, answer score: 3
Revisions (0)
No revisions yet.