Analysis of dynamic algorithms in Knuth's model

AbstractThis paper analyzes the average behaviour of algorithms that operate on dynamically varying data structures subject to insertions I, deletions D, positive (resp. negative) queries Q+ (resp. Q-) under the following assumptions: if the size of the data structure is k (k ϵ N), then the number of possibilities for the operations D and Q+ is a linear function of k, whereas the number of possibilities for the ith insertion or negative query is equal to i. This statistical model was introduced by Françon [6,7] and Knuth [12] and differs from the model used in previous analyses [2–7]. Integrated costs for these dynamic structures are defined as averages of costs taken over the set of all their possible histories (i.e. evolutions considered up to order isomorphism) of length n. We show that the costs can be calculated for the data structures serving as implementations of linear lists, priority queues and dictionaries. The problem of finding the limiting distributions is also considered and the linear list case is treated in detail. The method uses continued fractions and orthogonal polynomials but in a paper in preparation, we show that the same results can be recovered with the help of a probabilistic model