TY - GEN

T1 - On the Dynamic Finger Conjecture for splay trees extended abstract

AU - Cole, Richard

PY - 1990

Y1 - 1990

N2 - The Dynamic Finger Conjecture for splay trees states that the cost of m searches on an n-node splay tree is O(m + n + Σ log(|ij - ij-1$/|), where the sum is from i = 1 to m and the jth access is to the ijth item in symmetric order (the i0th item is the item originally at the root of the tree). In other words, the amortized cost of an access is O(1 + log d), where the current access is at distance d from the previous access (distance being measured in terms of the number of items straddled by the two successive accesses); in addition, there is an additive O(n) initialization cost. A bound on the cost is obtained.

AB - The Dynamic Finger Conjecture for splay trees states that the cost of m searches on an n-node splay tree is O(m + n + Σ log(|ij - ij-1$/|), where the sum is from i = 1 to m and the jth access is to the ijth item in symmetric order (the i0th item is the item originally at the root of the tree). In other words, the amortized cost of an access is O(1 + log d), where the current access is at distance d from the previous access (distance being measured in terms of the number of items straddled by the two successive accesses); in addition, there is an additive O(n) initialization cost. A bound on the cost is obtained.

UR - http://www.scopus.com/inward/record.url?scp=0025137205&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025137205&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0025137205

SN - 0897913612

T3 - Proc 22nd Annu ACM Symp Theory Comput

SP - 8

EP - 17

BT - Proc 22nd Annu ACM Symp Theory Comput

PB - Publ by ACM

T2 - Proceedings of the 22nd Annual ACM Symposium on Theory of Computing

Y2 - 14 May 1990 through 16 May 1990

ER -