Nisan comments on The correct response to uncertainty is *not* half-speed

[Nisan]

I can get O(k).