Let $u_1,\ldots,u_n$ be a sequence of rationals with finite binary expansion. Consider the following simple averaging algorithm:
while the sequence is not monotone increasing, pick $i$ with $u_{i+1}<u_i$; then replace $[u_i,u_{i+1}]$ by $[\frac12(u_i+u_{i+1}-1),\frac12(u_i+u_{i+1}+1)]$.
It is not difficult to see that the algorithm will stop after a finite number of steps. I am interested in good lower and upper bounds on the maximal number $A_n(s)$ of steps the algorithm takes if initially $|u_i|\le s$, and the maximal number $B_n(s)$ of steps the algorithm takes if initially $|u_i|\le is$, when $s$ is large.
The answer depends on how the index is picked; possibly the best choice is to take the smallest index $i$ with maximal $u_i-u_{i+1}$. So I am primarily interested in this case, and perhaps a proof of its optimality or a counterexample.
