$O$ нотация

$\leq$

$O$ (big-O) нотация используется для описания верхней асимптотической границы времени исполнения алгоритма.
В анализе алгоритмов, $O$ зачастую дает оценку времени выполнения в наихудшем случае, показывая, что алгоритм не будет расти быстрее заданного предела при увеличении размера входных данных.
$O$ не описывает типичное или среднее время выполнение работы, однако дает верхний предел асимптотического роста.

$O$ пример:

Время выполнения алгоритма Quicksort имеет верхнюю асимптотическую границу $O(n^2)$.
В наихудшем случае, когда на вход подается обратно отсортированный массив (или при постоянном неудачном выборе опорного элемента), время выполнения Quicksort вырастет квадратично относительно размера входа.
Это значит, что асимптотически Quicksort не будет выполнять свою работу медленнее чем $O(n^2)$ ни при каких вводных данных.

$\Omega$ нотация

$>=$

$\Omega$ (Omega) нотация используется для описания нижний асимптотической границы исполнения алгоритма.
$\Omega$ задает минимальный асимптотический порядок роста, ниже которого время исполнения алгоритма не может опуститься при увеличении входных данных.

$\Omega$ пример:

Quicksort имеет нижнюю асимптотическую границу $\Omega(n \log n)$, то есть алгоритм не может иметь асимптотический рост менее, чем $n \log n$.

$\Theta$ notation

$\approx$

$\Theta$ (Theta) нотация описывает точную (тесную) границу асимптотического роста времени исполнения алгоритма.
Она комбинирует $\Omega$ и $O$, описывая насколько быстро растет время исполнения алгоритма для определенного случая.

• Если $O = \Omega$, тогда $\Theta = O = \Omega$
• Если $O \neq \Omega$, тогда мы описываем по отдельности
  • лучший случай $\Theta$
  • средний случай $\Theta$
  • худший случай $\Theta$

$\Theta$ пример:

Quicksort

Поэтому:

• лучший случай $\Theta(n \log n)$
• средний случай $\Theta(n \log n)$
• худший случай $\Theta(n^2)$

Mergesort

Поэтому:

• $\Theta(n \log n)$ (нет нужды в описании разных случаев)