Если максимально простым язом, то big o - это верхняя граница роста исследуемой функции за исключением граничных случаев.
Для обозначения асимптоты для худшего случая используется омега (хуже чем омега, исследуемая функция не растёт).
Вот у классического квиксорта есть граничный случай, который проявляется на отсортированных или почти отсортированными последовательностях - у него возникает N^2, где N - количество элементов.
Автор вопроса по сути спрашивает, можно ли как-то модифицировать квиксорт так, чтобы этих граничных случаев не было.
big o в таком случае будет равняется омеге и оба будут nlogn
