It also follows from the above discussion that the lattice size, that is, the number of edges, is also linear in the sentence length, i.e., O(|E|) = O(n).
since the node degree is at most α (i.e., not dependent on n), the lattice path can be efficiently reranked in O(n) time by using dynamic programming.