[hyperation]

Is it just me or the Big O algebra at the end doesn't seem right?

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

[otasevic]

thanks for this comment. I realized that I skipped a few steps in the explanation, so I am updating it now.

But essentially you see that the equation is S^2 - S - 2L < 0

from that, you can solve that the roots of the function are: (1) 1/2 + sqrt(2L) and (2) 1/2 - sqrt(2L)

That means that (S-1/2-sqrt(2L)) * (S-1/2+sqrt(2L)) < 0

The second term is always positive, which means that we need to make the first term negative in order for the inequality to hold.

=> S < 1/2 + sqrt(2L) which leads to O(sqrt(L)) when you let L approach infinity.

Does this make sense?