TY - GEN

T1 - The asymptotic evolution of data structures

AU - Maier, Robert S.

N1 - Funding Information:
*This work was supportedi n part by AFOSR grant 88-0189.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1990.

PY - 1990

Y1 - 1990

N2 - The evolution of certain pointer-based implementations of dictionaries, linear lists and priority queues is studied. Under the assumption of equiprobability of histories, i.e., of paths through the internal state space of the implementation, the n → ∞ asymptotics of the space and time costs of a sequence of n supported operations are computed. For list implementations the mean integrated spatial cost is asymptotically proportional to n2, and its standard deviation to n3/2. For d-heap implementations of priority queues the mean integrated space cost grows only as n2/√log n, i.e. more slowly than the worst-case integrated cost. The standard deviation grows as n3/2. These asymptotics reflect the convergence as n → ∞ of the normalized structure sizes to datatype-dependent deterministic functions of time, as earlier discovered by Louchard. This phenomenon is clarified with the aid of large deviation theory, and path integral techniques.

AB - The evolution of certain pointer-based implementations of dictionaries, linear lists and priority queues is studied. Under the assumption of equiprobability of histories, i.e., of paths through the internal state space of the implementation, the n → ∞ asymptotics of the space and time costs of a sequence of n supported operations are computed. For list implementations the mean integrated spatial cost is asymptotically proportional to n2, and its standard deviation to n3/2. For d-heap implementations of priority queues the mean integrated space cost grows only as n2/√log n, i.e. more slowly than the worst-case integrated cost. The standard deviation grows as n3/2. These asymptotics reflect the convergence as n → ∞ of the normalized structure sizes to datatype-dependent deterministic functions of time, as earlier discovered by Louchard. This phenomenon is clarified with the aid of large deviation theory, and path integral techniques.

KW - Dynamic data structures

KW - Expected costs

KW - Large deviations

KW - Stochastic modelling

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

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

U2 - 10.1007/3-540-53504-7_57

DO - 10.1007/3-540-53504-7_57

M3 - Conference contribution

AN - SCOPUS:85032205081

SN - 9783540535041

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 13

EP - 23

BT - Advances in Computing and Information – ICCI 1990 - International Conference on Computing and Information, Proceedings

A2 - Koczkodaj, Waldemar W.

A2 - Akl, Selim G.

A2 - Fiala, Frantisek

PB - Springer-Verlag

T2 - International Conference on Computing and Information, ICCI 1990

Y2 - 23 May 1990 through 26 May 1990

ER -