1
$\begingroup$

Maybe I am wrong, but I read that when we categorise problems in their respective complexity classes, we use worse-case analysis.

Why don't we use the average case?

I imagine we could have a problem in NP when we look at it's worse-case, but when we look at it's average-case we could have a really efficient algorithm. This is just intuition and not sure of an example.

For something like cryptography, I'm guessing this is not desirable.

$\endgroup$
4
$\begingroup$

Because average case requires a definition of "average". Specifically, average over what distribution of inputs?

Worst-case does at least give you an objective guarantee: whatever input you consider, it won't be worse than this. That sort of guarantee still has some value even if the worst-case inputs aren't representative of what you're going to be doing.

On the other hand, average-case doesn't necessarily correspond to anything very much. Suppose you just take the uniform distribution over inputs of a given length. Why would you feel that the mean number of steps the algorithm takes is a useful measure of anything? Probably your inputs don't look much like a uniform distribution. The mean based on any distribution doesn't give you any guarantees about actual performance on specific instances.

Also, and this might, sadly, be the real reason, average-case complexity is hard. It means you have to understand how the algorithm behaves on essentially all possible inputs, and getting good bounds for all kinds of input is a lot of work.

One place where average-case is used is amortized analysis. Consider a dynamically sized hash table where, if the table is more than, say, three-quarters full, you copy everything into a new table that's double the size. In this situation, inserting an element into a table of size $n$ can take up to $2n$ steps, which is horrible in the worst case. However, you only need to do this expensive copying operation once every $3n/4$ steps. On average, then, each insert operation causes $2n/(3n/4)=8/3$ amount of the work needed to double the size of the hash table. So, in a very strong sense, the average cost of growing the table is just a constant amount per insertion, and this is completely independent of what insertions are done. This is practically very useful when analyzing algorithms that use hash tables.

$\endgroup$
1
$\begingroup$

If you want to categorize a problem in a way that makes it comparable to other problems, then you need to categorize it the same way as everyone else does.

If you are only interested in one particular problem, then you can analyze it any way you like. You might look at the worst case, or the average case, or you can analyze "typical" cases, whatever "typical" means. For example, for NP-complete decision problems you often have instance where the answer isn't just "Yes" or "No" but "obviously yes" or "obviously no", and these instances may be easy to solve, even though the problem is NP complete. And the instances that you usually encounter might fall into the "easy" cases.

Note that "average" may be very hard to define.

$\endgroup$

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.