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?