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

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.)