1
$\begingroup$

I've constructed an algorithm on (rooted) binary trees, where the running time at a node depends on the size of its smaller subtree, where we compute from each leaf upwards towards the root.
More specifically, at each node, a constant amount of time is required for each node in the smallest of its 2 subtrees.

The running time for a tree with $n$ nodes is then easily bounded by $O(n^2)$, however, I conjecture that the running time is bounded by $O(n \log n)$, since I think $\sum_{x\in V(T)}\min(|V_l(x)|, |V_r(x)|) \leq O(n \log n)$ holds.

How would I go about proving this?

$\endgroup$
  • 1
    $\begingroup$ Yes, I mean the smaller of the 2 subtrees given by the children. For a linear tree, each node will require constant time, since the smaller subtree has 1 node, and the larger has n-1 nodes. Giving O(n) $\endgroup$ – b9s Nov 6 '18 at 13:34
  • $\begingroup$ In fact, in the case of a linear tree, the smaller subtree has 0 node. So it take 0 time to compute a linear tree. Or do you want to add a constant time for the node itself? That sound more reasonable. $\endgroup$ – Apass.Jack Nov 6 '18 at 14:04
  • $\begingroup$ Well, there is always some setting of values at a node, so you can assume some constant time. The best-case behaviour is not what interests me though. Note that $sum_{x\in V(T)}min(...) + O(1) = n*O(1) + sum_{x \in V(T)} min(...)$ $\endgroup$ – b9s Nov 6 '18 at 14:41
1
$\begingroup$

A nice question!

As the OP has pointed out, it is enough to show the following inequality for any tree $T$ of $n\gt0$ nodes, where for any node $x$, $l(x)$ is the number of nodes in the left subtree of $x$ and $r(x)$ is the number of nodes in the right subtree of $x$.

$$\sum_{x\in V(T)}\min(l(x), r(x)) \leq n \log n$$

Proof by mathematical induction.

  • base case when $n=1$. Both side is 0.
  • Suppose it is true when the number of nodes in the tree is smaller than $n$. Let us consider a tree $T$ with $n>1$ node. Let the left subtree $T_l$ of the root node has $p$ node and the right subtree $T_r$ of the root node has $n-1-p$ node. There are two cases.
    • $p=0$ or $p=n-1$ is easy.
    • $p\neq0$ and $p\neq n-1$. (This case is only possible when $n\ge3$.) WLOG assume $p\le n-1-p$; otherwise we can switch the left subtree and the right subtree.

$$\begin{aligned} &\sum_{x\in V(T)}\min(l(x), r(x)) \\ &= \min(p, n-1-p) + \sum_{x\in V(T_l)}\min(l(x), r(x))+\sum_{x\in V(T_r)}\min(l(x), r(x))\\ &\leq p + p\log p +(n-1-p)\log(n-1-p)\\ &= p + p\log p +p\log(n-1-p) + (n-1-2p)\log(n-1-p)\\ &= p + p\log (p(n-1-p)) + (n-1-2p)\log n\\ &\le p + p\log \left((\frac{n-1}2)^2\right) + (n-1-2p)\log n\\ &\le p + 2p\log \left(\frac{n}2\right) + (n-1-2p)\log n\\ &= (1- 2\log2)p + (n-1)\log n\\ &\le n\log n \end{aligned}$$

Proof is done. Note that we have actually proved a tighter upper bound, $\frac1{2}n \log_2 n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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