We perform here a perturbated worst case analysis of classical algorithms. This kind of analysis have been introduced by Spielman & al. (under the name ``smooth analysis'') for continuous problems. We deal here with the complexity of discrete algorithms. It is natural to expect that the higher the perturbation is, the more the discrete smooth complexity will be near from the average case complexity. Similarly, the lower the perturbation is, the more the discrete smooth complexity will be near from the worst case complexity. However, a complete description of the transition between the two regimes appear to be a nontrivial task. In this paper, by two kinds of natural parametrizations, we study the transition between the two regimes for well-known algorithms such as left-to-right maxima counting, quicksort, shortest path.
Back to the Index