# What is the asymptotic time complexity of the following 2 recurrences?

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

and

$$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{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)}$.