Привет всем.

У меня возникла проблема.
Необходимо сравнить результаты сортировки массивов разными способами с теоретическими
т.е берется некий масссив к примеру из 100 эл. и сортируется одним из методов сортировки.
При этом подсчитывается количество серий в массиве, количество пересылок М и количество сравнений С. С этим проблем нет.
Но существуют некие формулы по которым можно теоретически расчитать минимально, среднее и максимальное количество сравнений и пересылок.
Может кто поможет с пониманием вот этих выражений на конкретном значении n=100

Для прямого выбора
M = 3(n-1) - ну тут конечно ясно - (n-1)=99*33=292 чтото вроде того
С=n^2-n/2 - тоже понятно 4950

Метод пузырька (вот тут и начинается морока)
С=n^2-n/2 - тоже как в методи прямого выбора 4950 - вопросов нет
Для определения М тут нужно выявить минимальное и максимальное М а вот среднее М которое мне и нужно якобы вычисляется по вормуле
Mсред=О(n^2) -так вот чему равно О? Сколько читал нигде не написано. Как выявить О, от чего оно зависит.

шейкерная сортировка
Mсред=О(n^2)
Ссред=О(n2)

Это теоретические значения они зависят от величины N т.е для них при определенных значениях N вполне можно расчитать  M и C. Если конкретно то мне нужны теоретичесике цифры для 100,200,300 и 500 элементных массивов
для всех видов сортировки
Кто нибудь пожалуйста объясните человеческим а не книжным языком.

Про О-большое можно смотреть, например, первый авзац этого текста

википедия


Так что
O(n^2) = const*n^2

Про точное значение const надо что-нибудь ещё читать.

Можно попробовать третий том Кнута.