True, but for the same big O they can salt the password for each user and compare it to what they have stored. My big pet peeve (that I've actually seen) is when they say your password is too similar to an old one. I have no idea how that could be reasonably done if they're storing your password correctly.