Smoothed analysis: introduction

• Analyzing an arbitrary instance leads to the worst case