Average Case Complexity Rivisted I got confused with the analysis of algorithms in average case. Following is the my perception regarding average case using sorting problem:


  Suppose we have a 5 elements array to be sorted using Insertion sort.
  Time complexity will depend upon the particular arrangements of
  elements in the array. Usually, when algorithm's time complexity
  depends upon the particular ordering of elements or different instances of same
  problem size n, then different cases (i.e. best, average and worst)
  occurs. In the above example there are 5!=120 possible instances of
  problem size 5. For a instance, when elements are already sorted,
  algorithms takes lowest time, and that will be best case. For another
  instance, when elements are reverse sorted, it takes longest time, and
  that will be worst case. there are still 118 instances left. For
  average case time complexity, we should take average of running
  times for all possible input instances (including 118 left and 2
  others). That means we should take average of all 120 running time for
  different 120 instances.


Why probability distribution plays a role while computing average case time complexity? Why don't we just take a simple average of running times for all possible input instances of same problem size?
If the distribution on input instances is uniform, then the two are equivalent.  Talking about a distribution has two potential advantages: (1) it allows us to analyze the algorithm using the tools of probability theory, which can sometimes be useful, (2) it allows us to meaningfully talk about average-case running time for a non-uniform distribution on inputs.