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

TheUp to a constant offset, the value $T(n)$ is the value of $x$ such that $y(x) = 1$$y = O(1)$, that is, such that $\text{li} (x) = (\log_2 n - 1)/\ln 2$. $$ 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 $$ 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...$$ T(n) \sim \frac{\log_2 n}{\log_2 \log_2 n} $$

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...

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} $$

Source Link
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...