Average complexity of the Jiang–Wang–Zhang pairwise tree alignment algorithm and of a RNA secondary structure alignment algorithm

We prove that the average complexity of the pairwise ordered tree alignment algorithm of Jiang, Wang and Zhang is in O(nm), where n and m stand for the sizes of the two trees, respectively. We show that the same result holds for the average complexity of pairwise comparison of RNA secondary structures, using a set of biologically relevant operations.