Bound the number of iterations to achieve certain accuracy I have an iterative algorithm and I want to know possible ways of bounding the number of iterations to achieve a desirable accuracy. And here is the description of the problem:
Let $f(x)$ be monotonically increasing function satisfies 


*

*$\lim_{x\rightarrow 0}f(x) = 0$;

*$f(x) > 0$ if $x > 0$;

*$f(x) < x$;


The iterative algorithm is as follows:


*

*choose a starting value, $x_0$;

*$x_{t+1} = x_{t} - f(x_{t})$, for $t = 0, 1, 2, \dots$;

*terminate when $x_{t+1} < \varepsilon$;


It is easy to show that $lim_{t\rightarrow0}x_{t} = 0$, but I also need to know for a given accuracy, $\varepsilon$, how much iterations are needed to drive $x_t$ below $\varepsilon$. An order of magnitude is sufficient. 
Thank you very much! 
 A: If you have good enough information on the behaviour of  $f(x)$ as $x \to 0+$, you may be able to produce bounds.  Thus suppose $c_1 x < f(x) < c_2 x$ for $0 < x \le x_0$, where $0 < c_1 < c_2 < 1$.  Then $(1-c_2)^t x_0 < x_t < (1-c_1)^t x_0$.
EDIT: Consider the case $f(x) = x/\ln(1/x)$ as the OP mentioned in a comment below.
Of course we want $0 < x_0 < 1/e$ for this to work: then $0 < x_t < 1/e$ and $x_t \to 0$ as $t \to \infty$.  Let $x_t = \exp(-\sqrt{b_t})$ so $b_t = \ln(1/x_t)^2$, $b_0 > 1$, and $b_t \to +\infty$ as $t \to \infty$, increasing monotonically.  We have $b_{t+1} = F(b_t)$ where
$$ \eqalign{F(b) &= \left(  \sqrt{b} - \ln \left(1 - \frac{1}{\sqrt{b}}\right)\right)^2\cr  
&= \left( \sqrt{b} + \sum_{n=1}^\infty b^{-n/2}/n  \right)^2\cr
&=b + 2 + \frac{1}{\sqrt{b}} + O(1/b)\ \text{as $b \to \infty$}} $$
In particular, $b_{t+1} > b_t + 2$ so $b_t > 1 + 2t$ and $x_t < \exp\left(-\sqrt{1+2t}\right)$.
On the other hand, for any $\epsilon > 0$ there is $T$ such that for $t \ge T$,
$F(b_t) < b_t + 2 + \epsilon$, so $b_t < b_T + (2+\epsilon) (t-T)$, and thus
$x_t > \exp\left(-\sqrt{b_T + (2+\epsilon)(t-T)}\right)$.  
