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.
The worst part is that if they know that password is already in use.... then they aren't storing their passwords appropriately.
You could store the passwords as hashes and just compare the hashed value.
yes, but then they are not salted, which is what they should be doing.
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.
But are they peppered?
Good call.