Also note that for any step size you choose S you will have to go O(N/s + s - 1), which goes from bad to good to bad again (in terms of running time as s goes from 2 - n/2. This tells us that there is a local maxima which we can find with the derivative of N/s + s - 1 with respect to s which is N/S^2 - 1. Set this equal to 0 and solve gives us s = Sqrt(N). Which gies us the optimal step size for arbitrary N.

The step-size method doesn’t minimize the worst-case running time, as already discussed.