Adding the swapping operation changes the time complexity for deterministic parsing from linear to quadratic in the worst case, but empirical estimates based on treebank data show that the expected running time is in fact linear for the range of data attested in the corpora.

Assuming that the calls 0(0) and 75(0) can both be performed in constant time, the worst-case time complexity of a deterministic parser based on a transition system S is given by an upper bound on the length of transition sequences in S.

As a result, the time complexity of deterministic parsing is 0(n2) in the worst case, which is rare, but 0(n) in the best case, which is common, and experimental results on data from five languages support the conclusion that expected running time is linear in the length of the sentence.

There is recent work on algorithms that can cope with important subsets of all non-projective trees in polynomial time (Kuhlmann and Satta, 2009; Gomez-Rodriguez et al., 2009), but the time complexity is at best 0(n6), which can be problematic in practical applications.

In Section 3, we first define a minimal transition system and explain how it can be used to perform projective dependency parsing in linear time; we then extend the system with a single transition for swapping the order of words in the input and demonstrate that the extended system can be used to parse unrestricted dependency trees with a time complexity that is quadratic in the worst case but still linear in the best case.

As noted in section 2, the worst-case time complexity of a deterministic transition-based parser is given by an upper bound on the length of transition sequences.

Let us now consider the time complexity of the extended system Su 2 (0, Tu, cs, Ct) and let us begin by observing that 2n is still a lower bound on the number of transitions required to reach a terminal configuration.