The upper bound is a best case analysis. In the best case, I can choose “1” to be my password, and no one will ever guess it.
In the worst case, we assume that the attacker has done their home work and knows the algorithm by which the password was generated, but not the content of this particular password. So, knowing the algorithm, what can the attacker exploit that would help them discover the contents of this password in the shortest possible time?
I submit that the worst case analysis is really the only one we care about.
My point is that that is not the worst case. Example of a worse case: the attacker knows that + the first 2 characters of your password (real-life example).
The worst case would probably be something like "attacker knows hash, passwd algorithm, full state of machine at passwd generation time incl. random seed and all characters of the password but one". It is clearly far worse than your case, though I find your case more relevant than this one.
In the worst case, we assume that the attacker has done their home work and knows the algorithm by which the password was generated, but not the content of this particular password. So, knowing the algorithm, what can the attacker exploit that would help them discover the contents of this password in the shortest possible time?
I submit that the worst case analysis is really the only one we care about.