# 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?

Getting detailed data for one instance is hard, getting them for each possible instance of size $$n$$ is worse, and then you have to average... assuming you do know the distribution of the input data in sufficient detail.
Take the well-plodded case of sorting. How would you characterize the distribution of the $$n!$$ possible permutations of $$n$$ elements (assuming they are all different!) real people throw at your program? It is said [citation needed] that "somewhat sorted" data are quite common. Presumably meaning starting with a large collection of sorted data and "append a bunch of unsorted data at the end", maybe "change a random selection of data in some way", or perhaps "add a (smallish) random value to each element", or a lot of other reasonable models depending on the case. A dictionary presumably works in the first way, a list of prices the second or third. OK, selected one, what exactly are the parameters of your distribution? It'll depend on the application. So you have your distribution, just setting up the equations to compute the average for size $$n$$ is a daunting task, let alone solve them.