A question about your computation for the upper bound on S.

**=> (S-1) + (S-2) + (S-3) + ….+ 1 < L**

**=> S*(S-1) / 2 < L**

**=> S < sqrt(2L + 1)**

How did you get to the last step? I think your transformation is wrong. It should be

S² < 2L + S

And now we can use the weak upper bound from before |S| < |L|:

=> S² < 2L + S < 3L

=> S < sqrt(3L) => S in O(sqrt(L))