The computational complexity of PTK is O(pρ (Moschitti, 2006a), where p is the largest subsequence of children that we want consider and ρ is the maximal outdegree observed in the two trees.
the average running time again tends to be linear for natural language syntactic trees (Moschitti, 2006a).