The terms |V|, id, |V'| and id' are all clearly O(n), but on the other hand neither |V| and id nor |V'| and id' are independent. Intuitively, if there are a lot of internal nodes in a tree, they will not have a very large internal degree. We address in this section, how this dependency will affect the running time for different types on trees.