What is the asymptotic time complexity of the following 2 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) &amp;\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 \\ &amp;\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 &gt; 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 &lt; 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) &amp;\approx n_0 \log n_0 \cdot n_1 \log n_1 \cdot n_2 \log n_2 \cdots \\ &amp;=
\frac{n_0^2}{n_1} \frac{n_1^2}{n_2} \frac{n_2^2}{n_3} \cdots \\ &amp;=
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.