Report Number: CS-TR-79-708
Institution: Stanford University, Department of Computer Science
Title: An analysis of a memory allocation scheme for implementing stacks
Author: Yao, Andrew C.
Date: January 1979
Abstract: Consider the implementation of two stacks by letting them grow towards each other in a table of size m . Suppose a random sequence of insertions and deletions are executed, with each instruction having a fixed probability p (0 < p < 1/2) to be a deletion. Let $A_p (m) denote the expected value of max{x,y}, where x and y are the stack heights when the table first becomes full. We shall prove that, as $m \rightarrow \infty$, $A_p (m) = \sqrt{m/(2 \pi (1-2p))} + O((log m)/ \sqrt{m})$. This gives a solution to an open problem in Knuth ["The Art of Computer Programming, Vol. 1, Exercise 2.2.2-13].
http://i.stanford.edu/pub/cstr/reports/cs/tr/79/708/CS-TR-79-708.pdf