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