1

We know that $D(1) = 0$.

Now from the inequality, $$D(n) \le D\left(\frac{2}{3}n\right) + 2$$

it should follow that $$D(n) \le 2\cdot \log_{\frac{3}{2}}(n).$$

*Edit: the logarithm has a base $\frac{3}{2}$

How do we get that last bound?

cubeception
  • 350
  • 2
    Is $D$ defined only on a subset of the natural numbers? Or of the rational numbers? – John Wayland Bales Aug 29 '17 at 22:56
  • 1
    I think must be defined at least on the rational numbers – Giuseppe Barbaro Aug 29 '17 at 23:04
  • $D(n)$ is supposed to be depth of a binary tree. The inequality is obtained by "balancing" the tree by taking a subtree that has $\frac{1}{3}< n\le \frac{2}{3}n$ leaves ouf of a tree and then connecting the subtree and the remainder to a new tree on second level, hence +2 (it's a communication protocol that's why it is a bit strange). – cubeception Aug 29 '17 at 23:07
  • 3
    You need to put some constraint on the value of $\frac{2n}{3}$ when $n$ is not a multiple of $3$. If one interpret $\frac{2n}{3}$ as $\lceil\frac{2n}{3}\rceil$, the inequality at $n = 2$ becomes $D(2) \le D(2) + 2$ which gives no information to $D(2)$. Even if we treat this as a special case and interpret $\frac{2\cdot}{3}$ as $1$, the inequality $D(n) \le 2 \log_{3/2} n$ can fail at $n = 5$. – achille hui Aug 29 '17 at 23:48
  • 1
    @achillehui I believe the untold assumptions that could make the conclusion hold true are: $,n \ge 1,$, inequalities to hold for $,n \ge 3/2,$, and $,D(n),$ monotonically increasing. – dxiv Aug 30 '17 at 01:18

1 Answers1

2

(Disclaimer: the following assumes this is one of those contexts where certain hand-waving is allowed/expected, otherwise see the posted comments for why the problem is not well posed.)

Let $\,n = (3/2)^k \iff k = \log_{3/2}(n)\,$, and define $T(k)=D\big((3/2)^k\big)=D(n)\,$, then:

$$ T(k)=D \left(\left(\frac{3}{2}\right)^k \right) \;\le\; D \left(\frac{2}{3} \cdot \left(\frac{3}{2}\right)^k \right) + 2 = D \left(\left(\frac{3}{2}\right)^{k-1} \right) + 2 = T(k-1) + 2 $$

Next, by telescoping and using that $T(0)=D(1)=0\,$:

$$ T(k) \le T(k-1)+ 1 \cdot 2 \le T(k-2) + 2 \cdot 2 \le \cdots \le T(0)+k \cdot 2 = 2k $$

Rewriting the latter in terms of $n\,$, it follows that $D(n) = T(k) \le 2 k = 2 \log_{3/2} n$.

dxiv
  • 76,497