I have an algorithm which operates on a rooted tree. It first recursively computes results for each of the root's child subtrees. It then does some work to combine them. The amount of work at the root is K^2 where K is the number of distinct values among the sizes of the subtrees.
What's the best bound on its runtime complexity? I haven't been able to construct a case in which it does more than linear work in the size of the tree.
This is governed by the Master Theorem of divide and conqour algorithms. For this particular case (me reading between the lines in what you have described) it is mainly determined by how much work it takes on a single node to combine the work compiled for K values in the subtrees. Specifically if it is less than K work, then the cost is dominated by the cost at the lowest level and would be O(K) in total, if the work at a given level is O(K) then the total work becomes O(K log(K)). For work at a level higher than O(K), it is dominated by the work at the higest level. We therefor have that your algorithm as a runtime complexity of O(K^2).
