Smoothed analysis: introduction

• Analyzing an arbitrary instance leads to the worst case

• Analyzing the complete problem space results in the average case