This kumite shows that tests are too strict.

That solution is strictly O(n), but iterates twice instead of once ( "O(2n)", which is O(n) ). But it times out -- unlike the solution it is based on, which iterates once.

If you require O(n), the constant factor should, within reason, not matter. I don't think this approach is unreasonable. Use fewer, bigger, tests to test performance.