← Back to Event List

Joint Applied Mathematics and Statistics Colloquium

Dr. Jim Fill, The Johns Hopkins University

Location

University Center : 115

Date & Time

April 7, 2017, 11:00 am12:00 pm

Description


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.