Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.