Skip to main content
1 of 2
David Harris
  • 3.5k
  • 1
  • 26
  • 38

Given an initial value of $n = 2^i$, the argument is gradually reduced so that after one stage it is $2^{i - \log i}$, and so forth. If we examine the exponent alone, it satisfies $$ i(0) = \log_ n, i(k+1) = i(k) - \log i(k) $$

We approximate this difference equation with the differential equation $$ y(0) = \log_2 n, y'(x) = -\log_2 y(x) $$ yielding $$ y(x) = \log_2 n - (\ln 2) \text{li}(x) $$ where $li$ is the logarithmic integral.

The value $T(n)$ is the value of $x$ such that $y(x) = 1$, that is, such that $\text{li} (x) = (\log_2 n - 1)/\ln 2$.

For $n$ sufficiently large we have $li(x) \sim x/\ln x$. Hence we should have $$ x \sim (\ln 2)^{-2} \ln n \ln \ln n $$ that is, $$ T(n) \sim (\log_2 n) (\log_2 \log_2 n) $$

Obviously I have left out a lot of details but this be basically right...

David Harris
  • 3.5k
  • 1
  • 26
  • 38