Skip to Main Content

Joint Applied Mathematics and Statistics Colloquium

Dr. Jim Fill, The Johns Hopkins University

Friday, April 7, 2017
11:00 AM - 12:00 PM
University Center : 115


Title: A local limit theorem for QuickSort key comparisons via multi-round smoothing


Abstract: It is a well-known result, due independently to Régnier (1989) and Rösler (1991), that the number of key comparisons required by the randomized sorting algorithm QuickSort to sort a list of  n  distinct items (keys) satisfies a global distributional limit theorem.  We resolve an open problem of Fill and Janson from 2002 by using a multi-round smoothing technique to establish the corresponding local limit theorem.

This is joint work with Béla Bollobás and Oliver Riordan.