Verification of minimum-redundancy prefix codes
A. Belal, Amr Elmasry · IEEE Transactions on Information Theory · 2006
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.