Perturbations on sequences?

• Now we have defined the notion of smoothed complexity.

• But it is not clear what the „neighborhood of an instance“ is.

• If we consider sorting, an instance is an arbitrary permutation of a sequence: