Tightest upper bound on length of distinguishing string in Hopcroft's algorithm
Let $Q$ be the set of states, $|Q|=n$. Consider the equivalence relation $E_i\subseteq Q\times Q$ of &quot;indistinguishability by strings of length at most i&quot;.
Let $k$ be the tightest upper bound. We have a pair of distinguishable states $p,q$ for which the shortest distinguishing string $w$ has length $k$, i.e., $(p,q)\in E_{k-1}\setminus E_{k}$. By reading the first letter $w_1$ of $w$ we also get a pair of states $(\delta(p,w_1),\delta(q,w_1))\in E_{k-2}\setminus E_{k-1}$ for which the shortest distinguishing word has length $k-1$ (it is the word $w_2\dots w_k$). We can continue the same argument down to $0$.
Therefore, $E_0\supsetneq E_1\supsetneq\dots\supsetneq E_{k-1}\supsetneq E_k= E_{k+1}=E_{k+2}\dots$.
The equivalence $E_0$ has two equivalence classes (parts): the accepting and the nonaccepting states. (Assuming that there is at least one accepting and at least one non-accepting state; otherwise nothing is distinguishable and the tightest bound is $-\infty$.) And any equivalence relation can have at most $n$ parts.
By the chain of strict inclusions above, $E_1$ has at least 3 parts, $E_2$ has at least $4$ parts, etc., and $E_{n-2}$ has (at least) $n$ parts which means that $E_{n-2}$ is the identity relation. This implies that the worst-case bound is $k=n-2$.
This bound is tight: Consider a two-element automaton with one accepting and one non-accepting state. We have $n=2$ and $k=0=n-2$.