Асимптотические классы эффективности алгоритмов - EcsFlash/DataTypes GitHub Wiki

Для того, чтобы можно было сравнивать между собой порядки роста и классифицировать их придумали три условных обозначения: O, Θ(тета), Ω(омега).

O-обозначение

говоря не строго, обозначение O(g(n)) - это множество всех функций, порядок роста которых при достаточно больших n не превышает некоторую константу, умноженную на значение функции g(n).(g(n)-любая неотрицательная функция на N)

Например, n ∈ O(n^2), 100n+5 ∈ O(n^2), n(n-1)/2 ∈ O(n^2). Это действительно так, ведь всё это линейные функции, у которых порядок роста <=n^2. А вот n^3∉O(n^2), так как функция является кубической.

Θ-обозначение

говоря не строго, обозначение Θ(g(n)) - это множество всех функций, порядок роста которых при достаточно больших n находится в "коридоре", созданном умножением некоторых двух констант на функцию g(n).

Например, любая квадратичная функция вида ax^2+bx+c ∈ Θ(n^2)

Ω-обозначение

говоря не строго, обозначение Ω(g(n)) - это множество всех функций, порядок роста которых при достаточно больших n не меньше некоторой константы, умноженной на значение g(n). Например n^3 ∈ Ω(n^2)

Кратко и на одной картинке:

Какая-то теорема

также можно использовать пределы для сравнения порядка роста