# Running time based on smallest subtree

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?

• 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) – b9s Nov 6 '18 at 13:34
• 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. – John L. Nov 6 '18 at 14:04
• 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(...)$ – b9s Nov 6 '18 at 14:41

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$$.