For occurrences of links x1 , x2 , the element of π at a row addressed by x 1 and a column addressed by x 2 is 1 if x 1 = x 2 , and 0 otherwise.
we conclude that function KARIZE() takes time O(L 3 ) for each synchronous tree γ, and the total running time is O(|G| , where Y is the set of synchronous tree pairs of G. The term |G| accounts for the reading of the input, and dominates the complexity of the algorithm only in case there are very few links in each synchronous tree pair.