Based on birthday attack, you need to generate at least 2^n/2 of possible combination to have 50% chance of finding a password. I have a list of 3000 random password make from 16 characters of upper, lower characters(That's 50^16 possible combinations) hashed into MD5. How many possible combinations i have to look up to find at least half the result of password list above?
I don't think that the birthday paradox applies here.
The birthday paradox states that in your case, if you have 4.6 × 1013 passwords, there is a 50% chance that two are the same.
However, you only have 3000 password hashes. So you would have to look up in the order of 5016/3000 passwords.
The chance that a random password is in your collection is 1-(1-1/5016)3000. If you try 1023 passwords you have a chance of (1-(1-1/5016)3000) × 1023 ≈ 20%.