Приклад використання нотації О-велике:

, бо існують

(наприклад,

) та

(наприклад,

), такі, що

для кожного

.
Асимптотична нотація великого О, відома також як нотація Ландау — поширена математична нотація для формального запису асимптотичної поведінки функцій. Широко вживається в теорії складності обчислень, інформатиці та математиці.
Названа нотацією Ландау на честь німецького математика Едмунда Ландау, який популяризував цю нотацію.
«О» велике. Нехай задані дві комплекснозначні функції
та
визначені в деякій множині
комплексної площини. Тоді говорять, що
якщо існує константа K >0, що виконується нерівність |f(z)| ≤ K |g(z)| для
.
«O» велике в околі
. Нехай
і
дві комплекснозначні функції визначені в деякій множині
комплексної площини, замикання якої містить точку
(тобто,
є граничною точкою
). Тоді ми пишемо
при
з
якщо існує число
таке, що
у сенсі означення «О» великого. Тобто,
обмежена величиною добутку константи на
для всіх
з
, які лежать досить близько до
.
«O» велике в нескінченності. Нехай
і
дві комплекснозначні функції визначені в необмеженій множині
комплексної площини. Тоді ми кажемо, що
при
з
якщо існує число
так що
,
у сенсі означення «О» великого. Тобто,
обмежена величиною добутку деякої константи на
, для достатньо великих
з
.
«o» маленьке. Нехай
і
дві комплекснозначні функції визначені в деякій множині
комплексної площини замикання якої містить точку
. Тоді ми кажемо, що
при
з
якщо для довільного
, як завгодно малого, існує відповідне йому
, що
для
і
.
Тобто,
є меншим за величиною за будь-який малий добуток
для
досить близьких до точки
.
«о» маленьке в нескінченності Нехай
і
комплекснозначні функції визначені в необмеженій множині
комплексної площини. Тоді ми пишемо
при
з
якщо для довільного
, як завгодно малого, ми можемо знайти відповідне
таке що
для
і
.
Функції f(x) та g(x) називають функціями одного порядку, якщо f(x) = O(g(x)) та g(x) є O(f(x)) для x
x0;
Часто для позначення того, що f(x) є O(g(x)) використовується запис f(x) = O(g(x)), хоч це не зовсім правильно і в деяких випадках може привести до плутанини.
Нехай
і
цілі числа. Якщо
, то
при
. Для доведення цього запишемо
Покладемо
. Тоді
означає що
, оскільки
. Отже, якщо
, нерівність
виконується при виборі
. Також, з аналогічним обмеженням на
та
, ми маємо, що
при
з
.
Для доведення цього запишемо
Виберемо, наприклад,
. Тоді,
означає, що
оскільки
.
Деякі важливі класи відношень[ред. | ред. код]
Графіки деяких поширених функцій.
Нижче наведений список класів функцій, які часто зустрічаються в аналізі алгоритмів. Тут n
∞, с — константа. Функції, які зростають повільніше, наведені першими.
нотація
|
назва
|
O(1)
|
константа
|
O(log n)
|
логарифмічне
|
O([log n]c)
|
полілогарифмічне
|
O(n)
|
лінійне
|
O(n · log n)
|
лінеарітмічне
|
O(n2)
|
квадратичне
|
O(nc)
|
поліноміальне
|
O(cn)
|
експоненціальне
|
O(n!)
|
факторіальне
|