Значение средней сложности при использовании нотации Big-O

Отвечая на этот вопрос дискуссия начал в комментариях о сложности QuickSort. Что я помню по университетскому времени, так это то, что QuickSort составляет O (n ^ 2) в худшем случае, O (n log (n)) в среднем случае и O ( n log (n)) (но с более жесткой границей) в лучшем случае.

Что мне нужно, так это правильное математическое объяснение значения средней сложности , чтобы ясно объяснить, что это значит для того, кто считает, что нотация большого O может использоваться только в худшем случае.

Что я помню, если то для определения средней сложности вы должны учитывать сложность алгоритма для всех возможных входов, посчитать сколько вырожденных и нормальных случаев. Если количество вырождающихся случаев, деленное на n, стремится к 0, когда n становится большим, тогда можно говорить о средней сложности общей функции для нормальных случаев.

Верно ли это определение или определение средней сложности отличается? И если это правильно, может ли кто-нибудь заявить об этом более строго, чем я?