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

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy