Asymptotics of repeated decrease by logarithmic part

Question

While trying to analyze an algorithm, I got the following recurrence relation: $x_{n+1} = x_n - \log_b (x_n)$ and $x_0 = N$ (large), i.e. in every iteration the problem size decreases by a logarithmic part. Now I want to know how many iterations (asymptotically) I will have to perform to solve an input of size $N$ (assuming, that I need only a constant number of iterations as soon as $x_i$ becomes $b$), like $argmin_i (x_i < b)$.

I think I was able to show that this behaves as $N / \log_B(N)$ but I was confused that I could find no reference to this problem. Is is too trivial to mention, or did I just not find the right places/names to search for this kind of function/decay?

Answer 1

Let $k=\min\{n:x_n< b\}$. Since $x_n$ is decreasing, $\log_bx_n\le\log_bN$, hence $k\ge(N-b)/\log_bN=(1+o(1))N/\log_bN$. On the other hand, fix any $\varepsilon>0$. Since $\log_bx_n\ge(\log_bN)/(1+\varepsilon)$ as long as $x_n\ge N^{1/(1+\varepsilon)}$, we can reach $x_n\le N^{1/(1+\varepsilon)}$ in at most $(1+\varepsilon)N/\log_bN$ steps, and then we get to $x_n\le b$ in at most $N^{1/(1+\varepsilon)}\le\varepsilon N/\log_bN$ additional steps, since $x_n$ decreases by at least $1$ in every step. Thus, for large enough $N$, $k\le(1+2\varepsilon)N/\log_bN$. Since $\varepsilon$ was arbitrary, $k=(1+o(1))N/\log_bN$. Yes, I’d call this “too trivial to mention”.

Answer 2

I'm guessing you can approximate it with the differential equation $$ x'(n) = -\log(x(n)). $$ The solution to this satisfies some equation involving the exponential integral special function, namely $x(n) = \exp(y(n))$ where $$ n - Ei(1,-y(n)) + Ei(1,-ln(N)) = 0 $$ and $$ Ei(1,z) = \int_1^\infty e^{-uz}u^{-1} du.$$ Maybe someone can disentangle that for us while I sleep (it's 2:20am here in Australia).