Analysis of Correctness and Running-Time

In this module, we analyze the correctness and amortized running time of operations on a ScapegoatTree.

Correctness

We first prove the correctness by showing that, when the add(x) operation results in a node that violates Condition (1 as discussed previously), then we can always find a scapegoat:

Lemma 1: Let $u$ be a node of $\text{depth } h > \log_{3/2}$ q in a ScapegoatTree. Then there exists a node $w$ on the path from $u$ to the root such that.

$$\frac{\text{size}(w)}{\text{size}(\text{parent}(w))} > 2/3$$

Proof: Suppose, for the sake of contradiction, that this is not the case, and

$$\frac{\text{size}(w)}{\text{size}(\text{parent}(w))} \leq 2/3$$

for all nodes $w$ on the path from $u$ to the root. Denote the path from the root to $u$ as $r$ = $u_0,...,u_{h} = u$. Then, we have $\text{size}(u_{0} ) =n,\text{size}(u_{1}) \leq \frac{2}{3} n, \text{size} \left ( u_{2} \right ) \leq \frac{4}{9} n$ and, more generally,

$$\text{size}(u_{i}) \leq \left ( \frac{2}{3} \right )^{i} n$$

But this gives a contradiction, since $\text{size}(u) \ge 1$, hence

$$1 \leq \text{size}(u) \leq \left ( \frac{2}{3} \right )^{h} n < \left ( \frac{2}{3} \right )^{log_{3/2}q} n \le \left(\frac{2}{3}\right)^{\log_{3/2} n} n = \left ( \frac{1}{n} \right ) n=1$$