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.


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 depth h>log3/2\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.

size(w)size(parent(w))>2/3\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

size(w)size(parent(w))2/3.\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 = u0,...,uh=u_0,...,u_{h} = u. Then, we have size(u0)=n,size(u1)23n,size(u2)49n\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,

size(ui)(23)in.\text{size}(u_{i}) \leq \left ( \frac{2}{3} \right )^{i} n.

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

1size(u)(23)hn <(23)log3/2qn(23)log3/2nn=(1n)n=11 \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