How to calculate the needed encryptions in salted passwords?
In your case, you say the salt only has 16 bits of entropy, which is pretty weak.

To see whether 'one particular password' was used, the attacker would have to attempt 65,536 possible Salt combinations, for each 'particular password' that must be tested. The number of users does not  matter because we have now established a need to brute-force the (weak) salt, and only try a single particular password.

On the other hand, with a properly implemented modern Password Hash, where sufficiently strong (e.g. 72 bits of entropy) salt is used, if the attacker fails to acquire the salt, then there would be no practical way for him to brute-force the hash.