Before revision:  In the particular case of one-sided errors on the input, it has expected time complexity O(x) where x is the position of the first marked element  .
After revision:  In the particular case of one-sided errors on the input, it has expected time complexity O(x) where x is the position of the first marked element . Compare with previous work, our algorithm can handle errors in the input oracle .