2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What would be average of (1,2,3)? Simply add all numbers and divide the sum by 3. Why don't we do it for calculating average time complexity. Yes I agree when probability distribution is uniform, both are equal. But why we talk about probabilty? Where it is useful? In my opinion this should be taken into account only in the case of randomized algorithms. $\endgroup$ – user3606704 Dec 11 '15 at 12:14
  • $\begingroup$ @user3606704 Because maybe the input distribution is not uniform. In most cases it will be, but in some (because for example the input data is generated from some real-world process) it won't. $\endgroup$ – Tom van der Zanden Dec 11 '15 at 12:47
  • $\begingroup$ "In most cases it will be": I'd rather say that in most case it won't be. We often resort to the uniform distribution for tractability of the calculation, not for realisticness. $\endgroup$ – Yves Daoust Dec 11 '15 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.