Average case complexity of Algo
What is meant by average case complexity of an algorithm?
- Average of complexity of all possible complexities over different inputs, OR
- Complexity of an input which is average of all possible inputs.
According to me when we say that average case complexity of Quicksort is
N log(N), I understand that it is for an input which is not skewed towards being already somewhat partially sorted nor being extremely unsorted. This complexity is for a random input, which (according to me) means an input which is average of all possible inputs. Hence the term average complexity.
Kindly correct me where I am wrong. And what average complexity actually means.