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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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$
    – Seeker
    Commented Dec 11, 2015 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
    Commented Dec 11, 2015 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$
    – user16034
    Commented Dec 11, 2015 at 16:58
0
$\begingroup$

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.

For a glimpse of the difficulties involved, the (very simple!) Shell sort routine has defied exact analysis except for limited cases, precisely because it scrambles data so that the second, third and following passes get "somewhat sorted" data to work on.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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