Well if you only change your password 3-4 times, you only have 4-5 options to try. You also kinda remember for most website if you changed your password a lot or not, so you naturally try the most plausible option first, at least in my experience.

If you regularly change your password, it can become a nightmare, i agree.