### GEORGE MASON
UNIVERSITY

DEPARTMENT OF MATHEMATICAL
SCIENCES

COLLOQUIUM

JANUARY 23, 2015

**Speaker: **
Jim Fill, Johns Hopkins University

**Title: ***
Probabilistic Analysis of QuickSort: An Overview
*

**Abstract:**
We will begin by reviewing the operation of the randomized sorting algorithm QuickSort, invented by Tony Hoare in the early 1960s. We will then survey the probabilistic analysis of QuickSort, from the solution of a simple divide-and-conquer recurrence relation for the expected value of the number of key comparisons $K_n$ needed to sort $n$ distinct keys (items), to three techniques for establishing and characterizing a limit distribution for normalized $K_n$, to rates of convergence to the limit distribution, to a recent more realistic analysis that treats keys as symbol strings and measures the execution cost of QuickSort as the number of symbol comparisons.

**Time:** Friday, January 23, 2015, 3:30-4:20 p.m.

**Place:** Exploratory Hall, room 4106

**Refreshments** will be served at 3:00 p.m.

Department of Mathematical Sciences

George Mason University

4400 University Drive, MS 3F2

Fairfax, VA 22030-4444

http://math.gmu.edu/

Tel. 703-993-1460, Fax. 703-993-1491