How is the average case evaluated in asymptotic notation?

The average case in asymptotic notation is estimated as the expected value of the algorithm's running time based on the distribution of input data. This means analyzing how many steps are needed on average if the input data is chosen randomly from a certain set with a given probability distribution.

For example, for a sorting algorithm, the average case is the average running time over all possible permutations of the input array. Unlike the worst case (maximum time) and the best case (minimum time), the average case provides a more realistic estimate of performance under typical conditions.

It is important to understand that estimating the average case requires knowing or assuming a probabilistic distribution of input data, which is not always possible.