Skip to main content
2 of 2
EDIT: I messed up this calculatin in my earlier answer. I think this fixes it.
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 $$ -\ln 2 li(y) = x - \ln 2 li(\log_2 n) $$ where $li$ is the logarithmic integral.

Up to a constant offset, the value $T(n)$ is the value of $x$ such that $y = O(1)$, that is, $$ T(n) = O(1) + \ln 2 li(\log_2 n) $$

For $n$ sufficiently large we have $li(x) \sim x/\ln x$. Hence we should have $$ T(n) \sim \frac{\log_2 n}{\log_2 \log_2 n} $$

David Harris
  • 3.5k
  • 1
  • 26
  • 38