The time complexity of PTK is O(pρ where p is the largest subsequence of children that one wants to consider and ρ is the maximal out-degree observed in the two trees.
the average running time again tends to be linear for syntactic trees (Moschitti, 2006).