Type of case problem in algorithm.
“Average case” analysis is the calculation of the average running time of an algorithm under some assumption (ie about the relative frequencies (distribution) of different inputs that defines (domain|data) knowledge about the problem)
- Assuming that every possible input array is equally unlikely, and then analyze the average running time of an algorithm.
- Using a set of pre-specified benchmarks. Benchmarks data set are known data set:
- where men agrees up front about some set.
- that represent practical or typical inputs
In worst-case analysis, by definition you're making absolutely no assumptions about where the input comes from beyond what the input length N was.
Worst case analysis is usually mathematically much more attractable than trying to analyze the average performance of an algorithm under some distribution over inputs.
Worst case is then usually easier to analyze than the average case.