Editing Splay tree (section)

== Performance theorems ==

There are several theorems and conjectures regarding the worst-case runtime for performing a sequence ''S'' of ''m'' accesses in a splay tree containing ''n'' elements.

{{Math theorem|Balance Theorem|The cost of performing the sequence ''S'' is <math>O\left[m \log n + n\log n\right]</math>.
  {{Math proof|Take a constant weight, e.g. {{tmath|1=w(x)=1}} for every node ''x''. Then {{tmath|1=W=n}}.}} 
This theorem implies that splay trees perform as well as static balanced binary search trees on sequences of at least ''n'' accesses.<ref name="SleatorTarjan" />}}

{{Math theorem|Static Optimality Theorem|Let <math>q_x</math> be the number of times element ''x'' is accessed in ''S''. If every element is accessed at least once, then the cost of performing ''S'' is <math>O\left[m + \sum_{x\in tree} q_x\log\frac{m}{q_x}\right]</math> 
  {{Math proof|Let <math>w(x)=q_x</math>. Then <math>W=m</math>.}} 
This theorem implies that splay trees perform as well as an optimum static binary search tree on sequences of at least ''n'' accesses.<ref>{{harvnb|Knuth|1997|p=478}}</ref> They spend less time on the more frequent items.<ref name="SleatorTarjan" /> Another way of stating the same result is that, on input sequences where the items are drawn independently at random from a non-uniform [[probability distribution]] on ''n'' items, the amortized expected ([[average-case analysis|average case]]) cost of each access is proportional to the [[Entropy (information theory)|entropy]] of the distribution.{{sfnp|Grinberg|Rajagopalan|Venkatesan|Wei|1995}}}}

{{Math theorem|Static Finger Theorem|Assume that the items are numbered from 1 through ''n'' in ascending order. Let ''f'' be any fixed element (the 'finger'). Then the cost of performing ''S'' is <math>O\left[m + n\log n + \sum_{x\in sequence} \log(|x-f| + 1)\right]</math>.
  {{Math proof|Let <math>w(x)=1/(|x-f|+1)^2</math>. Then {{tmath|1=W=O(1)}}. The net potential drop is ''O'' (''n'' log ''n'') since the weight of any item is at least {{tmath|1=1/n^2}}.<ref name="SleatorTarjan" />}} }}

{{Math theorem|Dynamic Finger Theorem|Assume that the 'finger' for each step accessing an element ''y'' is the element accessed in the previous step, ''x''. The cost of performing ''S'' is <math>O\left[m + n + \sum_{x,y\in sequence}^m \log(|y-x| + 1)\right]</math>.<ref name="ColeEtAl">{{harvnb|Cole|Mishra|Schmidt|Siegel|2000}}.</ref><ref name="Cole">{{harvnb|Cole|2000}}.</ref>}}

{{Math theorem|Working Set Theorem|At any time during the sequence, let <math>t(x)</math> be the number of distinct elements accessed before the previous time element x was accessed.  The cost of performing ''S'' is <math>O\left[m + n\log n + \sum_{x\in sequence} \log(t(x) + 1)\right]</math> 
  {{Math proof|Let <math>w(x)=1/(t(x)+1)^2</math>. Note that here the weights change during the sequence. However, the sequence of weights is still a permutation of {{tmath|1=1, \tfrac 1 4, \tfrac 1 9, \cdots, \tfrac 1 {n^2} }}. So as before {{tmath|1=W=O(1)}}. The net potential drop is ''O'' (''n'' log ''n'').}} 
This theorem is equivalent to splay trees having [[key-independent optimality]].<ref name="SleatorTarjan" />}}

{{Math theorem|Scanning Theorem|Also known as the '''Sequential Access Theorem''' or the '''Queue theorem'''.  Accessing the ''n'' elements of a splay tree in symmetric order takes ''O''(''n'') time, regardless of the initial structure of the splay tree.<ref name="Tarjan">{{harvnb|Tarjan|1985}}.</ref> The tightest upper bound proven so far is <math>4.5n</math>.<ref name="Elmasry">{{harvnb|Elmasry|2004}}.</ref>}}