# Splay tree amortized analysis cost using Access Lemma

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