How is it possible to authenticate a message of n bytes in O(1)? Or are you talking about fixed size blocks and the time to authenticate is O(block_size)?
He means that message of equal size authenticate in constant time, regardless of which bits are set; that is not true of all authentication constructions.