What is the complexity of these tree-based algorithms?

Question

Suppose we have a balanced binary tree, which represents a recursive partitioning of a set of $N$ points into nested subsets. Each node of the tree represents a subset, with the following properties: subsets represented by two children nodes of the same parent are disjoint, and their union is equal to the subset represented by the parent. The root represents the full set of points, and each leaf represents a single distinct point. So there are $\log N$ levels to the tree, and each level of the tree represents a partitioning of the points into increasingly fine levels of granularity.

Now suppose we have two algorithms, each of which operates on all of the subsets of the tree. The first does $O(D^2)$ operations at each node, where $D$ is the size of the subset represented by the node. The second does $O(D \log D)$ operations at each node. What is the worst case runtime of these two algorithms?

We can easily bound the first algorithm as $O(N^2 \log N)$, because it does $O(N^2)$ work at each of $\log N$ levels of the tree. Similarly, we can bound the second algorithm as $O(N \log ^2 N)$, by similar reasoning.

The question is, are these bounds tight, or can we do better? How do we prove it?

Answer 1

Apply the master theorem.

The first algorithm takes $O(N^2)$ time because your underlying recurrence is

\[ T(N) = 2T(N/2) + N^2 \]

The second algorithm takes $N\log^2N$ time as you mention. If your work per node is as indicated (and is tight) then this bound is tight as well.

Update: as commenters point out, the assumption here is that the tree is weight-balanced: each child has half the nodes of the parent. This would imply the log N height bound you indicate, but is not implied by it.