5
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ How do you do the splits into sub-trees? Equal number of nodes in each sub-tree? $\endgroup$
    – Aryabhata
    Mar 21, 2012 at 14:41
  • $\begingroup$ Yes. As Suresh inferred, that (or something similar) must be the case for the log N depth bound to hold. Sorry if that wasn't more explicitly stated. $\endgroup$
    – Dang
    Mar 21, 2012 at 18:39
  • $\begingroup$ Please edit the question to mention that explicitly. $\endgroup$
    – Aryabhata
    Mar 22, 2012 at 18:25

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Do you mean $\Theta$? Also, maybe an explanation as to how you obtained the recursion (and where the anchor went) would be helpful. Also, I do not see the OP mentioning that the work is partitioned into equal parts (which your recursion suggests). $\endgroup$
    – Raphael ♦
    Mar 21, 2012 at 12:42
  • $\begingroup$ @Raphael “the bound is tight” means that this is the best $O$ we can give. It is equivalent to “what we wrote as $O$ is a $\Theta$ for the worst case” (not $\Theta$ for all cases, which would be a lot stronger). The work is partitioned to equal parts up to the necessary precision (this would take a little work to be made precise) because the tree is balanced. $\endgroup$
    – Gilles 'SO- stop being evil'
    Mar 21, 2012 at 13:08
  • $\begingroup$ @Gilles: As this is an elementary question, I think more care should be taken to explain exactly those points as they should not be confused. A beginner can not know which characteristics can be ignored because they fall below the "necessary precision". $\endgroup$
    – Raphael ♦
    Mar 21, 2012 at 13:13
  • 2
    $\begingroup$ Actually this reasoning might be incorrect. The trees are height balanced (if I understand the question correctly), and need not be weight balanced, So the recursion you start with need not be correct in the first place. Of course, one could interpret the question to do an equal split at each node (and that is probably what was intended) in which case, this is right. $\endgroup$
    – Aryabhata
    Mar 21, 2012 at 14:09
  • $\begingroup$ The points are well taken. I did assume an even split based on the wording of the question (log n levels) $\endgroup$
    – Suresh
    Mar 21, 2012 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.