A tight lower bound for the train reversal problem

Abstract

In a 1987 Scientific American Computer Recreations article, A.K. Dewdney posed the problem of reversing an n-car train on a track with a one-car spur using the minimum amount of work. In that article, Dewdney indicated an algorithm for reversing the train that uses O(n3) work. Shortly thereafter, Amato, Blum, Irani and Rubinfeld (Reversing Trains: A Turn of the Century Sorting Problem, J. Algorithms, Vol. 10, 1989, pp. 413-428) discovered a simple recursive algorithm that requires O(n2logn) work to reverse a train. In this paper, we prove that Amato et al.'s algorithm is optimal up to a constant factor, i.e., we prove that any algorithm for reversing an n-car train in the Dewdney model requires Ω(n2log n) work. © 1990.