Average

“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)

Example:

• 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

Worst

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.