MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
It is a routine enough derivation to assign as undergraduate homework. Perhaps you will find a reference there. It feels like something Knuth would assign as a warm up exercise for the exercises in the book Concrete Mathematics. Gerhard "Ask Me About System Design" Paseman, 2011.09.08 – Gerhard Paseman Sep 8 '11 at 15:58
Is it $\log_b(x_n)$ or $\lfloor \log_b(x_n)\rfloor$? – Noam D. Elkies Sep 8 '11 at 16:27
@Noam: This does not make any difference. – Emil Jeřábek Sep 8 '11 at 16:49

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.