# Prove that a sequence of increasing find operations on a splay tree takes $\mathcal{O}(n)$ time

When studying about splay trees, I found the following statement:

Suppose we have a splay tree and a sequence of Find operations, where the elements we are searching for are in increasing order. Then the total time necessary to run the sequence is $$\mathcal{O}(n)$$ ($$n$$ is the number of nodes in the tree).

I looked around, but haven't been able to find anything. Can this be proven formally? Or shown that it is true?

• Please add a reference to the original source. Jan 30 '19 at 12:17
• What is $n$? $n$ cannot be the number of Find operations. Is $n$ the number of all nodes in the tree? Jan 30 '19 at 15:53
• Yes, sorry about that, it's the number of nodes in the tree. Edited the question. Jan 30 '19 at 18:15
• This fact should have been proved somewhere. Since I could not find it, I just wrote an answer. Jan 30 '19 at 19:44

Here is a helper fact.

(Simple cost of splaying) Let $$c(v)$$ be the time it takes to find an element $$v$$ in a splay tree. There exists a constant $$c_0$$ independent of the splay tree and $$v$$ such that $$c(v)\le c_0d(v)$$, where $$d(v)$$ is the depth of $$v$$.

Here is the sketch of a proof.

There are two tasks that contribute to $$c(v)$$.

• To locate $$v$$ by going from the root downwards to the $$v$$, which takes at most $$c_1d(v)$$ time for some constant $$c_1$$.
• To splay $$v$$ to the root. It takes each splay operation of zig, zag, zig-zig, zag-zag, zig-zag, zag-zig some constant time to move $$v$$ nearer to the root by 1 or by 2, splaying $$v$$ to the root takes at most $$c_2d(v)$$ time for some constant $$c_2$$.

Let $$c_0=c_1+c_2$$. Proof is done.

Suppose we have a splay tree and a sequence of Find operations, where the elements we are searching for are in increasing order. Then the total time necessary to run the sequence is $$O(n)$$, where $$n$$ is the number of nodes in the tree.

Let $$v_0, v_1,\cdots, v_m$$ be an array of elements in increasing order.

It takes $$O(n)$$ to find $$v_0$$ (including splaying $$v_0$$ to the root).

What about finding the remaining $$m$$ elements?

• Finding $$v_1$$ when $$v_0$$ is at the root takes at most $$c_0d_{v_0}(v_1)$$ time, where $$d_{v_0}(v_1)$$ is the depth of $$v_1$$ in the splay tree with $$v_0$$ as the root. Note that splay tree is a binary search tree, $$d_{v_0}(v_1)$$ is at most one one more than the number of elements between $$v_0$$ and $$v_1$$ exclusively.
• Finding $$v_2$$ when $$v_1$$ is at the root takes at most $$c_0d_{v_1}(v_2)$$ time, where $$d_{v_1}(v_2)$$ is at most one one more than the number of elements between $$v_1$$ and $$v_2$$ exclusively.
• $$\vdots$$
• Finding $$v_{m}$$ when $$v_{m-1}$$ is at the root takes at most $$c_0d_{v_{m-1}}(v_m)$$ time, where $$d_{v_{m-1}}(v_m)$$ is at most one more than the number of elements between $$v_{m-1}$$ and $$v_m$$ exclusively.

So, the total time necessary to run the sequence of finding $$v_1, v_2,\cdots,v_m$$ is at most $$c_0d(v_0, v_m)$$, where $$d(v_0, v_m)$$ is at most one more than the number of elements between $$v_0$$ and $$v_m$$ exclusively, i.e., $$d(v_0, v_m)\le m\lt n$$.

So the total time necessary to run the sequence of finding $$v_0, v_1, v_2,\cdots,v_m$$ is at most $$O(n) + c_0n$$, which is $$O(n)$$ still.