While investigating the complexity of a problem the start point is complexity for a single input and then running time of an algorithm starts to depend the distribution of the instances.When
we talking about a distribution of the instances ,there might be differences from the worst-case running time.Therefore the complexity can be better than worst case for the many of the