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