Anything that uses the standard decoding strategy (Viterbi) is quadratic in the number of "states" (i.e., tags), though, and that easily dominates.

(Nowadays, many people just use greedy---linear in the number of states---decoding because it rarely is much worse.)