1
$\begingroup$

Currently studying for an algorithms exam and I came across this question and solution, but I can't understand the solution where it references nodes of depth less than $4\log n$ and not restructuring. I understand everything else except for the $4\log n$ part - thanks in advance.

The question:

Suppose that when we perform search on a splay tree containing $n$ items we splay the deepest accessed node only when its depth is at least $4\log n$. Show that the total amortised cost of $m$ searches, where $m \ge n$, is $O(m \log n)$.

The solution:

Here we apply the Access Lemma, assigning weight 1 to all items. Then the size $s(x)$ of a node $x$ satisfies $1 \le s(x) \le n$ and the rank $r(x)$ satisfies $0 \le r(x) \le \log n$. By the Access Lemma the amortised cost of splay is bounded by $1 + 3 \log n = O(\log n)$. Moreover the amortised cost of searching for a node of depth less than $4\log n$ equals the actual cost, which is $O(\log n)$, since the tree is not restructured. Thus the total amortised cost of $m$ searches is $O(m \log n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.