We show that verifying a given prefix code for optimality requires
$\Omega(n\log{n})$, indicating that the verification problem is not
asymptotically easier than the construction problem. Alternatively,
we give linear-time verification algorithms for several special cases that
are either typical in practice or theoretically interesting.
DIMACS Home Page