Verification of minimum-redundancy prefix codes

We show that verifying a given prefix code for optimality requires /spl Omega/(nlogn) time, 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.