Adopting a greedy approach, on an arbitrary level during the tree-building, once we decide to merge a certain pair of constituents, say U j and U j+1 , we only need to recompute a small number of chains, i.e., the chains which originally include U j or U j+1 , and inference on each chain takes O(1).
the total time complexity is (n − 1) × O(1) + (n − 1) × O(1) = O(n), where the first term in the summation is the complexity of computing all chains on the bottom level, and the second term is the complexity of computing the constant number of chains on higher levels.