You could get faster in expected value. What if the time on input of length n was an expected value of 100 + 1/n?
That isn't possible, but it might not quite be obvious why that isn't possible.
That isn't possible, but it might not quite be obvious why that isn't possible.
To have sub-constant time it would have to go to 0 as n increases, as otherwise we could bound the time below by a constant. This isn't possible, as a computer will take at least 1 time unit on every input. So the expected time will always be at least 1.