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?