A new approach: Smoothed Complexity

• combines the strenghts of both worst case and average case analysis

• first introduced in 2001 by Daniel A. Spielman (MIT) and Shang-Hua Teng (University of Illinois) for the Simplex Method in Linear Programming

• smooth analysis of Quicksort was done by Cyril Banderier, René Baier and Kurt Mehlhorn in April 2003