Skip to main content
2 of 2
finish the proof; added 12 characters in body
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

$$T(n) = \frac{\log_2 n}{\log_2\log_2 n}$$ is a near-solution of the difference equation for large $n$. I expect this is the correct rate of growth and probably one can prove that by bounding the error term.

In fact there seems to be an asymptotic solution that starts $$T(n) = \frac{\log_2 n }{\log_2\log_2 n }\left(1 + \frac{1}{\log\log_2 n} + \frac{2}{(\log\log_2 n )^2} + \cdots \right),$$ where I left off the subscript on the log a few times on purpose.

So let's finish the proof. For constants $c,C$, define $$T_{c,C}(n) = \frac{\log_2 n }{\log_2\log_2 n }\left(1 + \frac{c}{\log\log_2 n}\right) + C.$$ By direct calculation, there is an $n_0$ such that for $n\ge n_0$ $$T_{c,C}(n)-T_{c,C}(n/\log_2 n) ~~\begin{cases} {}\lt 1 \text{ if $c=0$}\\\\ {}\gt 1 \text{ if $c=1$.}\end{cases} $$ (Note that $n_0$ is independent of $C$.) The recurrence for $T(n)$ starting at $n\gt n_0$ always lands in the interval $I=[n_0/\log_2 n_0,n_0]$. Choose constants $C_0,C_1$ such that $$T_{0,C_0}(n) \lt T(n) \lt T_{1,C_1}(n)$$ for $n\in I$, then induction shows it to be true for $n\gt n_0$ too.

In summary, we have proved that as $n\to\infty$, $$T(n) = \frac{\log_2 n }{\log_2\log_2 n }\left(1 + \frac{O(1)}{\log\log_2 n}\right).$$

Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147