Say we only know the worst case and best case complexity of an algo (Algo is not known). Is it possible to get the average case complexity?

+2 votes

Say we only know the worst case and best case complexity of an algo (Algo is not known). Is it possible to get the average case complexity?

0 votes

Answer will be NO, let me explain with example.

Suppose we have three number 5, 6, 7

So we are finding average = (5 + 6 + 7 ) / 3

So if we talk about a algorithm then the input will vary i.e input range and its value.

So to find average we need to consider all possible input values then only we can know the behavior of algorithm with input value.

So to find average case complexity we need to consider all possible inputs, not only best case and worst case as we can not guess the behavior of algo for other inputs.

...