$$T(n) = (\log n) \cdot T(n/\log n) + \Theta(n^i \cdot (\log n)^k)$$


$$T(n) = (n\log n) \cdot T(n/\log n) + \Theta(n^i \cdot (\log n)^k)$$

for any given $i$ and $k$.

I think it helps to know that for $0<j\leq 1$

\begin{equation} \lim_{n\to\infty} \frac{n/n^j}{n/\log n} = 0. \end{equation}

But what is a simple way to derive the asymptotic time complexity for the two given recurrences?


For the first recurrence, let $n_0 = n$ and $n_{t+1} = n_t/\log n_t$. As long as $n_t \geq \sqrt{n}$, we have $n_{t+1} \leq n_t/\log \sqrt{n_t} = n_t/((1/2)\log n)$, and so we reach $\sqrt{n}$ in $\log_{(1/2)\log n} n \approx \log n/\log \log n$ steps. It takes us another $\approx (1/2) \log n/\log \log n$ steps to get to $\sqrt[4]{n}$, and so on. If you do the calculation in full, you will probably find out that $n_m = O(1)$ for $m = O(\log n/\log\log n)$. In other words, for a constant fraction of the sequence $n_0,\ldots,n_m$, the value of $\log n_t$ is $\Theta(\log n)$. This justifies the approximation $n_t \approx n/\log^t n$. Under this approximation, we find out that (ignoring the $\Theta$) $$ \begin{align*} T(n) &\approx n^i \log^k n + \log n \cdot (n/\log n)^i \log^k n + \log^2 n \cdot (n/\log^2 n)^i \log^k n + \cdots \\ &\approx n^i \log^k n + n^i \log^{k-(i-1)} n + n^i \log^{k-2(i-1)} n + \cdots \end{align*} $$ The answer now depends on the value of $i$. If $i > 1$ then the terms keep decreasing, and so we expect $T(n) \approx n^i \log^k n$. If $i = 1$ then the terms are roughly the same size. Since there are roughly $\frac{\log n}{\log \log n}$ of them, we expect the answer to be $T(n) \approx \frac{\log n}{\log \log n} n^i \log^k n$. If $i < 1$ then the terms keep increasing, and so we expect the major contribution to come from $$\log n_0 \log n_1 \log n_2 \cdots T(\mathit{const}).$$ By definition, $\log n_t = n_t/n_{t+1}$, and so $$ \log n_0 \log n_1 \log n_2 \cdots = \frac{n_0}{n_1} \frac{n_1}{n_2} \frac{n_2}{n_3} \cdots \approx n. $$ So in this case, $T(n) \approx n$.

If we do the same for your second recurrence, we get $$ T(n) \approx n^i \log^k n + n \log n \cdot (n/\log n)^i \log^k n + n \log n \cdot (n/\log n) \log n (n/\log^2 n)^i \log^k n + n \log n \cdot (n/\log n) \log n \cdot (n/\log^2 n) \log n (n/\log^3 n)^i \log^k n + \cdots \approx \sum_{t=0}^m \frac{(n \log n)^t}{\log^{\binom{t}{2}}n} (n/\log^t n)^i \log^k n = n^i \log^k n\sum_{t=0}^m n^t \log^{-t(i-1)-\binom{t}{2}} n $$ Let us denote the $t$th term in the sum above by $S_t$. Then $$ \frac{S_{t+1}}{S_t} = \frac{n}{\log^{i+t+1} n}. $$ For the largest $t$ we consider, $\log^t n \approx n$, and so we expect the largest term to be near the end. This implies that $$ \begin{align*} T(n) &\approx n_0 \log n_0 \cdot n_1 \log n_1 \cdot n_2 \log n_2 \cdots \\ &= \frac{n_0^2}{n_1} \frac{n_1^2}{n_2} \frac{n_2^2}{n_3} \cdots \\ &= n_0 n_1 n_2 \cdots. \end{align*} $$ The approximation $n_t \approx n/\log^t n$ seems harder to justify in this context, but it should give us a ballpark estimate: $$ n_0 n_1 n_2 \cdots \approx n \cdot \frac{n}{\log n} \cdot \frac{n}{\log^2 n} \cdots \approx \frac{n^{m+1}}{\log^{\binom{m}{2}} n}. $$ We chose $m$ so that $\log^m n \approx n$, and so we expect the ratio to be $n^{\Theta(m)}$. In other words, $T(n) \approx n^{\Theta(\log n/\log \log n)}$.

All the estimates above are non-rigorous, and for this reason, they could be wrong. However, they point the way toward a more rigorous treatment.

| cite | improve this answer | |
  • $\begingroup$ Thanks for the help, especially with the 2nd case. It's appreciated! $\endgroup$ – Karim El Sheikh May 14 '18 at 19:46

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.