Two N Minus One

At most $2n - 1$ states for $n \ge 2$ and at most $\Theta(n\sigma)$ transitions for $n \ge 3$, built online in linear time for a constant alphabet.

At most $2n - 1$ states for $n \ge 2$ and at most $3n - 4$ transitions for $n \ge 3$, built online in linear time for a constant alphabet.

At most $n$ states for $n \ge 2$ and at most $n$ transitions for $n \ge 3$, built online in linear time for a constant alphabet.

$\Theta(n \log n)$ states for $n \ge 2$ and $\Theta(n \log n)$ transitions for $n \ge 3$, built offline in $\Theta(n \log n)$ for a constant alphabet.