[danbruc]

What do you think is wrong, I did not notice any really obvious mistake? Admittedly you would miss the improved bound unless you actually modified the implementation to abort further evaluation once you reach the maximum speed that still allows stopping, but I assume that is implied. I also guess one could even further improve the exponent to 1.25 by taking advantage of the fact that the maximum speed that still allows stopping decreases from left to right but I did not actually think it through, it is just my intuition that you would gain another square root.

[danbruc]

Being able to improve the exponent to 1.25 is probably wrong. After thinking about it more carefully I think you end up with a number of steps proportional to the generalized harmonic number of order -0.5 of L which seems to be Θ(n^1.5) but I am not really sure about that.