Programs without specification have only surprising behaviour no bugs. As far as I can see "reject!" does not specify complexity, so in this sense it would be completely fine. Additionally it claims to change the array instantly every time the block is called, which doesn't seem to give any other options than making it at least quadratic (presuming flat representation for arrays). This feels quite overspecified as accessing the array from within the block seems quite unusual case to cater for.

Though, this behaviour was changed after all which leaves me wondering how much Ruby people care about backward compatibility.