# Analysis of Correctness and Running Time

Understand the need of correctness and running time to implement scapegoat trees.

We'll cover the following

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$