Нотація Ландау

Нотація Ландау — поширена математична нотація для формального запису асимптотичної поведінки функцій. Широко вживається в теорії складності обчислень, інформатиці та математиці.

Названа нотацією Ландау на честь німецького математика Едмунда Ландау, який популяризував цю нотацію.

Означення для функцій дійсного (комплексного) аргументу

Через ${\displaystyle \mathbb {K} }$ позначимо ${\displaystyle \mathbb {R} }$ або ${\displaystyle \mathbb {C} }$. Нехай ${\displaystyle A\subset \mathbb {K} }$, ${\displaystyle f,g:A\to \mathbb {K} }$ і ${\displaystyle x_{0}}$ — гранична точка множини ${\displaystyle A}$. Через ${\displaystyle B(x_{0},\delta )}$ позначимо ${\displaystyle \delta }$-окіл точки ${\displaystyle x_{0}}$.

Функція ${\displaystyle f}$ називається підпорядкованою функції ${\displaystyle g}$ при ${\displaystyle x\to x_{0}}$, якщо існують дійсні додатні числа ${\displaystyle L}$ та ${\displaystyle \delta }$ такі, що для довільного ${\displaystyle x\in A\cap B(x_{0},\delta )\setminus \{x_{0}\}}$ виконується нерівність ${\displaystyle |f(x)|\leqslant L|g(x)|.}$

Для ${\displaystyle \mathbb {K} =\mathbb {R} }$ функція ${\displaystyle f}$ називається підпорядкованою функції ${\displaystyle g}$ при ${\displaystyle x\to +\infty }$, якщо існують дійсне додатнє число ${\displaystyle L}$ і дійсне ${\displaystyle C}$ такі, що для довільного ${\displaystyle x\in A\cap (C,+\infty )}$ виконується нерівність ${\displaystyle |f(x)|\leqslant L|g(x)|.}$

Для ${\displaystyle \mathbb {K} =\mathbb {C} }$ функція ${\displaystyle f}$ називається підпорядкованою функції ${\displaystyle g}$ при ${\displaystyle x\to \infty }$, якщо існують дійсне додатнє число ${\displaystyle L}$ і дійсне ${\displaystyle C}$ такі, що для довільного ${\displaystyle x\in A\cap \{z\in \mathbb {C} \mid |z|>C\}}$ виконується нерівність ${\displaystyle |f(x)|\leqslant L|g(x)|.}$

Позначення: ${\displaystyle f(x)=O(g(x))}$, ${\displaystyle x\to x_{0}}$ або ${\displaystyle f=O(g)}$, ${\displaystyle x\to x_{0}}$.

Означення для функцій цілого невід'ємного аргументу

Нехай ${\displaystyle f,g:\mathbb {N} \cup \{0\}\to \mathbb {R} _{+}}$. Функція ${\displaystyle f}$ називається підпорядкованою функції ${\displaystyle g}$ якщо існують додатнє дійсне число ${\displaystyle C}$ і натуральне ${\displaystyle n_{0}}$ такі, що для довільного ${\displaystyle n\geqslant n_{0}}$ виконується нерівність ${\displaystyle f(n)\leqslant Cg(n).}$

Позначення: ${\displaystyle f(n)=O(g(n))}$ або ${\displaystyle f=O(g)}$.

Також кажуть, що «${\displaystyle f}$ зростає не швидше ніж ${\displaystyle g}$» або «${\displaystyle g}$ є асимптотичною верхньою оцінкою ${\displaystyle f}$».

1. ${\displaystyle C\cdot f=O(f),x\to x_{0}}$ для довільного ${\displaystyle C\in \mathbb {K} .}$
2. ${\displaystyle C=O(1)}$ для довільного ${\displaystyle C\in \mathbb {K} .}$
3. Якщо ${\displaystyle \lim \limits _{x\to x_{0}}\left|{\frac {f(x)}{g(x)}}\right|\in \mathbb {R} }$, то ${\displaystyle f=O(g),x\to x_{0}.}$
4. Якщо ${\displaystyle f=O(h),x\to x_{0}}$ і ${\displaystyle g=O(h),x\to x_{0}}$, то ${\displaystyle f+g=O(h),x\to x_{0}.}$
5. Якщо ${\displaystyle f=O(g),x\to x_{0},}$ то ${\displaystyle f+g=O(g),x\to x_{0}.}$
6. Якщо ${\displaystyle f_{1}=O(g_{1}),x\to x_{0}}$ і ${\displaystyle f_{2}=O(g_{2}),x\to x_{0},}$ то ${\displaystyle f_{1}\cdot f_{2}=O(g_{1}\cdot g_{2}),x\to x_{0}.}$
7. Якщо ${\displaystyle f_{1}=O(g_{1}),x\to x_{0}}$ і ${\displaystyle f_{2}=O(g_{2}),x\to x_{0},}$ то ${\displaystyle f_{1}+f_{2}=O(\max(g_{1},g_{2})),x\to x_{0}.}$
8. Якщо ${\displaystyle f=O(g),x\to x_{0}}$ і ${\displaystyle g=O(h),x\to x_{0},}$ то ${\displaystyle f=O(h),x\to x_{0}.}$ (транзитивність)

Означення для функцій дійсного (комплексного) аргументу

Через ${\displaystyle \mathbb {K} }$ позначимо ${\displaystyle \mathbb {R} }$ або ${\displaystyle \mathbb {C} }$. Нехай ${\displaystyle A\subset \mathbb {K} }$, ${\displaystyle f,g:A\to \mathbb {K} }$ і ${\displaystyle x_{0}}$ — гранична точка множини ${\displaystyle A}$. Через ${\displaystyle B(x_{0},\delta )}$ позначимо ${\displaystyle \delta }$-окіл точки ${\displaystyle x_{0}}$.

Кажуть, що функція ${\displaystyle f}$ підпорядковує функцію ${\displaystyle g}$ при ${\displaystyle x\to x_{0}}$, якщо існують дійсні додатні числа ${\displaystyle L}$ та ${\displaystyle \delta }$ такі, що для довільного ${\displaystyle x\in A\cap B(x_{0},\delta )\setminus \{x_{0}\}}$ виконується нерівність ${\displaystyle |f(x)|\geqslant L|g(x)|.}$

Для ${\displaystyle \mathbb {K} =\mathbb {R} }$ кажуть, що функція ${\displaystyle f}$ підпорядковує функцію ${\displaystyle g}$ при ${\displaystyle x\to +\infty }$, якщо існують дійсне додатнє число ${\displaystyle L}$ і дійсне ${\displaystyle C}$ такі, що для довільного ${\displaystyle x\in A\cap (C,+\infty )}$ виконується нерівність ${\displaystyle |f(x)|\geqslant L|g(x)|.}$

Для ${\displaystyle \mathbb {K} =\mathbb {C} }$ кажуть, що функція ${\displaystyle f}$ підпорядковує функцію ${\displaystyle g}$ при ${\displaystyle x\to \infty }$, якщо існують дійсне додатнє число ${\displaystyle L}$ і дійсне ${\displaystyle C}$ такі, що для довільного ${\displaystyle x\in A\cap \{z\in \mathbb {C} \mid |z|>C\}}$ виконується нерівність ${\displaystyle |f(x)|\geqslant L|g(x)|.}$

Позначення: ${\displaystyle f(x)=\Omega (g(x))}$, ${\displaystyle x\to x_{0}}$ або ${\displaystyle f=\Omega (g)}$, ${\displaystyle x\to x_{0}}$.

Означення для функцій цілого невід'ємного аргументу

Нехай ${\displaystyle f,g:\mathbb {N} \cup \{0\}\to \mathbb {R} _{+}}$. Кажуть, що функція ${\displaystyle f}$ підпорядковує функцію ${\displaystyle g}$ якщо існують додатнє дійсне число ${\displaystyle C}$ і натуральне ${\displaystyle n_{0}}$ такі, що для довільного ${\displaystyle n\geqslant n_{0}}$ виконується нерівність ${\displaystyle f(n)\geqslant Cg(n).}$

Позначення: ${\displaystyle f(n)=\Omega (g(n))}$ або ${\displaystyle f=\Omega (g)}$.

Також кажуть, що «${\displaystyle f}$ зростає не повільніше ніж ${\displaystyle g}$» або «${\displaystyle g}$ є асимптотичною нижньою оцінкою ${\displaystyle f}$».

1. ${\displaystyle g=O(f),x\to x_{0}}$ тоді й лише тоді, коли ${\displaystyle f=\Omega (g),x\to x_{0}.}$
2. ${\displaystyle C\cdot f=\Omega (f),x\to x_{0}}$ для довільного ${\displaystyle C\in \mathbb {K} \setminus \{0\}.}$
3. ${\displaystyle C=\Omega (1)}$ для довільного ${\displaystyle C\in \mathbb {K} \setminus \{0\}.}$
4. Якщо ${\displaystyle \lim \limits _{x\to x_{0}}\left|{\frac {g(x)}{f(x)}}\right|\in \mathbb {R} }$, то ${\displaystyle f=\Omega (g),x\to x_{0}.}$
5. Якщо ${\displaystyle f=\Omega (h),x\to x_{0}}$ і ${\displaystyle g=\Omega (h),x\to x_{0}}$, то ${\displaystyle f+g=\Omega (h),x\to x_{0}.}$
6. Якщо ${\displaystyle f=\Omega (g),x\to x_{0},}$ то ${\displaystyle f+g=\Omega (g),x\to x_{0}.}$
7. Якщо ${\displaystyle f_{1}=\Omega (g_{1}),x\to x_{0}}$ і ${\displaystyle f_{2}=\Omega (g_{2}),x\to x_{0},}$ то ${\displaystyle f_{1}\cdot f_{2}=\Omega (g_{1}\cdot g_{2}),x\to x_{0}.}$
8. Якщо ${\displaystyle f_{1}=\Omega (g_{1}),x\to x_{0}}$ і ${\displaystyle f_{2}=\Omega (g_{2}),x\to x_{0},}$ то ${\displaystyle |f_{1}|+|f_{2}|=\Omega (\min(g_{1},g_{2})),x\to x_{0}.}$
9. Якщо ${\displaystyle f=\Omega (g),x\to x_{0}}$ і ${\displaystyle g=\Omega (h),x\to x_{0},}$ то ${\displaystyle f=\Omega (h),x\to x_{0}.}$ (транзитивність)

Означення для функцій дійсного (комплексного) аргументу

Через ${\displaystyle \mathbb {K} }$ позначимо ${\displaystyle \mathbb {R} }$ або ${\displaystyle \mathbb {C} }$. Нехай ${\displaystyle A\subset \mathbb {K} }$, ${\displaystyle f,g:A\to \mathbb {K} }$ і ${\displaystyle x_{0}}$ — гранична точка множини ${\displaystyle A}$. Через ${\displaystyle B(x_{0},\delta )}$ позначимо ${\displaystyle \delta }$-окіл точки ${\displaystyle x_{0}}$.

Функція ${\displaystyle g}$ називається асимптотичною точною оцінкою функції ${\displaystyle f}$ при ${\displaystyle x\to x_{0}}$, якщо існують дійсні додатні числа ${\displaystyle L_{1},}$ ${\displaystyle L_{2}}$ та ${\displaystyle \delta }$ такі, що для довільного ${\displaystyle x\in A\cap B(x_{0},\delta )\setminus \{x_{0}\}}$ виконується нерівність ${\displaystyle L_{1}|g(x)|\leqslant |f(x)|\leqslant L_{2}|g(x)|.}$

Для ${\displaystyle \mathbb {K} =\mathbb {R} }$ функція ${\displaystyle g}$ називається асимптотичною точною оцінкою функції ${\displaystyle f}$ при ${\displaystyle x\to +\infty }$, якщо існують дійсні додатні числа ${\displaystyle L_{1},}$ ${\displaystyle L_{2}}$ і дійсне ${\displaystyle C}$ такі, що для довільного ${\displaystyle x\in A\cap (C,+\infty )}$ виконується нерівність ${\displaystyle L_{1}|g(x)|\leqslant |f(x)|\leqslant L_{2}|g(x)|.}$

Для ${\displaystyle \mathbb {K} =\mathbb {C} }$ функція ${\displaystyle g}$ називається асимптотичною точною оцінкою функції ${\displaystyle f}$ при ${\displaystyle x\to \infty }$, якщо існують дійсні додатні числа ${\displaystyle L_{1},}$ ${\displaystyle L_{2}}$ і дійсне ${\displaystyle C}$ такі, що для довільного ${\displaystyle x\in A\cap \{z\in \mathbb {C} \mid |z|>C\}}$ виконується нерівність ${\displaystyle L_{1}|g(x)|\leqslant |f(x)|\leqslant L_{2}|g(x)|.}$

Позначення: ${\displaystyle f(x)=\Theta (g(x))}$, ${\displaystyle x\to x_{0}}$ або ${\displaystyle f=\Theta (g)}$, ${\displaystyle x\to x_{0}}$.

Означення для функцій цілого невід'ємного аргументу

Нехай ${\displaystyle f,g:\mathbb {N} \cup \{0\}\to \mathbb {R} _{+}}$. Функція ${\displaystyle g}$ називається асимптотичною точною оцінкою функції ${\displaystyle f}$ якщо існують дійсні додатні числа ${\displaystyle C_{1},}$ ${\displaystyle C_{2}}$ і натуральне ${\displaystyle n_{0}}$ такі, що для довільного ${\displaystyle n\geqslant n_{0}}$ виконується нерівність ${\displaystyle C_{1}g(n)\leqslant f(n)\leqslant C_{2}g(n).}$

Позначення: ${\displaystyle f(n)=\Theta (g(n))}$ або ${\displaystyle f=\Theta (g)}$.

1. ${\displaystyle f=\Theta (g),x\to x_{0}}$ тоді й лише тоді, коли ${\displaystyle f=O(g),x\to x_{0}}$ і ${\displaystyle g=\Omega (f),x\to x_{0}.}$
2. ${\displaystyle f=\Theta (g),x\to x_{0}}$ тоді й лише тоді, коли ${\displaystyle g=\Theta (f),x\to x_{0}.}$

Означення для функцій дійсного (комплексного) аргументу

Через ${\displaystyle \mathbb {K} }$ позначимо ${\displaystyle \mathbb {R} }$ або ${\displaystyle \mathbb {C} }$. Нехай ${\displaystyle A\subset \mathbb {K} }$, ${\displaystyle f,g:A\to \mathbb {K} }$ і ${\displaystyle x_{0}}$ — гранична точка множини ${\displaystyle A}$. Через ${\displaystyle B(x_{0},\delta )}$ позначимо ${\displaystyle \delta }$-окіл точки ${\displaystyle x_{0}}$.

Функція ${\displaystyle f}$ називається знехтуваною у порівнянні з функцією ${\displaystyle g}$ при ${\displaystyle x\to x_{0},}$ якщо для довільного додатнього ${\displaystyle \varepsilon }$ існує додатнє ${\displaystyle \delta }$ таке, що для довільного ${\displaystyle x\in A\cap B(x_{0},\delta )\setminus \{x_{0}\}}$ виконується нерівність ${\displaystyle |f(x)|\leqslant \varepsilon |g(x)|.}$

Для ${\displaystyle \mathbb {K} =\mathbb {R} }$ функція ${\displaystyle f}$ називається знехтуваною у порівнянні з функцією ${\displaystyle g}$ при ${\displaystyle x\to +\infty }$, якщо для довільного додатнього ${\displaystyle \varepsilon }$ існує додатнє ${\displaystyle C}$ таке, що для довільного ${\displaystyle x\in A\cap (C,+\infty )}$ виконується нерівність ${\displaystyle |f(x)|\leqslant \varepsilon |g(x)|.}$

Для ${\displaystyle \mathbb {K} =\mathbb {C} }$ функція ${\displaystyle f}$ називається знехтуваною у порівнянні з функцією ${\displaystyle g}$ при ${\displaystyle x\to \infty }$, якщо для довільного додатнього ${\displaystyle \varepsilon }$ існує додатнє ${\displaystyle C}$ таке, що для довільного ${\displaystyle x\in A\cap \{z\in \mathbb {C} \mid |z|>C\}}$ виконується нерівність ${\displaystyle |f(x)|\leqslant \varepsilon |g(x)|.}$

Позначення: ${\displaystyle f(x)=o(g(x))}$ або ${\displaystyle f=o(g).}$

Означення для функцій цілого невід'ємного аргументу

Нехай ${\displaystyle f,g:\mathbb {N} \cup \{0\}\to \mathbb {R} _{+}}$. Функція ${\displaystyle f}$ називається знехтуваною у порівнянні з функцією ${\displaystyle g}$, якщо для довільного додатнього ${\displaystyle C}$ існує натуральне ${\displaystyle n_{0}}$ таке, що для довільного ${\displaystyle n\geqslant n_{0}}$ виконується нерівність ${\displaystyle f(n)\leqslant Cg(n).}$

1. ${\displaystyle f=o(g),x\to x_{0}}$ тоді й лише тоді, коли ${\displaystyle \lim \limits _{x\to x_{0}}{\frac {f(x)}{g(x)}}=0.}$
2. Якщо ${\displaystyle f=o(g),x\to x_{0},}$ то ${\displaystyle f=O(g),x\to x_{0}.}$
3. Якщо ${\displaystyle f=o(g),x\to x_{0}}$ і ${\displaystyle g=O(h),x\to x_{0},}$ то ${\displaystyle f=o(h),x\to x_{0}.}$ Таким чином, ${\displaystyle o(O(h))=o(h),x\to x_{0}.}$ Аналогічно ${\displaystyle O(o(h))=o(h),x\to x_{0}.}$
4. Якщо ${\displaystyle f_{1}=o(g),x\to x_{0}}$ і ${\displaystyle f_{2}=o(g),x\to x_{0},}$ то ${\displaystyle f_{1}+f_{2}=o(g),x\to x_{0}.}$
5. Якщо ${\displaystyle f_{1}=o(g_{1}),x\to x_{0}}$ і ${\displaystyle f_{2}=O(g_{2}),x\to x_{0},}$ то ${\displaystyle f_{1}\cdot f_{2}=o(g_{1}\cdot g_{2}),x\to x_{0}.}$
6. Якщо ${\displaystyle f=o(g),x\to x_{0}}$ і ${\displaystyle g=o(h),x\to x_{0},}$ то ${\displaystyle f=o(h),x\to x_{0}.}$ (транзитивність)

Означення для функцій дійсного (комплексного) аргументу

Через ${\displaystyle \mathbb {K} }$ позначимо ${\displaystyle \mathbb {R} }$ або ${\displaystyle \mathbb {C} }$. Нехай ${\displaystyle A\subset \mathbb {K} }$, ${\displaystyle f,g:A\to \mathbb {K} }$ і ${\displaystyle x_{0}}$ — гранична точка множини ${\displaystyle A}$. Через ${\displaystyle B(x_{0},\delta )}$ позначимо ${\displaystyle \delta }$-окіл точки ${\displaystyle x_{0}}$.

Функція ${\displaystyle f}$ називається домінуючою у порівнянні з функцією ${\displaystyle g}$ при ${\displaystyle x\to x_{0},}$ якщо для довільного додатнього ${\displaystyle \varepsilon }$ існує додатнє ${\displaystyle \delta }$ таке, що для довільного ${\displaystyle x\in A\cap B(x_{0},\delta )\setminus \{x_{0}\}}$ виконується нерівність ${\displaystyle |f(x)|\geqslant \varepsilon |g(x)|.}$

Для ${\displaystyle \mathbb {K} =\mathbb {R} }$ функція ${\displaystyle f}$ називається домінуючою у порівнянні з функцією ${\displaystyle g}$ при ${\displaystyle x\to +\infty }$, якщо для довільного додатнього ${\displaystyle \varepsilon }$ існує додатнє ${\displaystyle C}$ таке, що для довільного ${\displaystyle x\in A\cap (C,+\infty )}$ виконується нерівність ${\displaystyle |f(x)|\geqslant \varepsilon |g(x)|.}$

Для ${\displaystyle \mathbb {K} =\mathbb {C} }$ функція ${\displaystyle f}$ називається домінуючою у порівнянні з функцією ${\displaystyle g}$ при ${\displaystyle x\to \infty }$, якщо для довільного додатнього ${\displaystyle \varepsilon }$ існує додатнє ${\displaystyle C}$ таке, що для довільного ${\displaystyle x\in A\cap \{z\in \mathbb {C} \mid |z|>C\}}$ виконується нерівність ${\displaystyle |f(x)|\geqslant \varepsilon |g(x)|.}$

Позначення: ${\displaystyle f(x)=\omega (g(x))}$ або ${\displaystyle f=\omega (g).}$

Означення для функцій цілого невід'ємного аргументу

Нехай ${\displaystyle f,g:\mathbb {N} \cup \{0\}\to \mathbb {R} _{+}}$. Функція ${\displaystyle f}$ називається домінуючою у порівнянні з функцією ${\displaystyle g}$, якщо для довільного додатнього ${\displaystyle C}$ існує натуральне ${\displaystyle n_{0}}$ таке, що для довільного ${\displaystyle n\geqslant n_{0}}$ виконується нерівність ${\displaystyle f(n)\geqslant Cg(n).}$

1. ${\displaystyle g=o(f),x\to x_{0}}$ тоді й лише тоді, коли ${\displaystyle f=\omega (g),x\to x_{0}.}$
2. ${\displaystyle f=\omega (g),x\to x_{0}}$ тоді й лише тоді, коли ${\displaystyle \lim \limits _{x\to x_{0}}\left|{\frac {f(x)}{g(x)}}\right|=+\infty .}$
3. Якщо ${\displaystyle f=\omega (g),x\to x_{0},}$ то ${\displaystyle f=\Omega (g),x\to x_{0}.}$
4. Якщо ${\displaystyle f=\omega (g),x\to x_{0}}$ і ${\displaystyle g=\Omega (h),x\to x_{0},}$ то ${\displaystyle f=\omega (h),x\to x_{0}.}$ Таким чином, ${\displaystyle \omega (\Omega (h))=\omega (h),x\to x_{0}.}$ Аналогічно ${\displaystyle \Omega (\omega (h))=\omega (h),x\to x_{0}.}$
5. Якщо ${\displaystyle f_{1}=\omega (g),x\to x_{0}}$ і ${\displaystyle f_{2}=\omega (g),x\to x_{0},}$ то ${\displaystyle f_{1}+f_{2}=\omega (g),x\to x_{0}.}$
6. Якщо ${\displaystyle f_{1}=\omega (g_{1}),x\to x_{0}}$ і ${\displaystyle f_{2}=\Omega (g_{2}),x\to x_{0},}$ то ${\displaystyle f_{1}\cdot f_{2}=\omega (g_{1}\cdot g_{2}),x\to x_{0}.}$
7. Якщо ${\displaystyle f=\omega (g),x\to x_{0}}$ і ${\displaystyle g=\omega (h),x\to x_{0},}$ то ${\displaystyle f=\omega (h),x\to x_{0}.}$ (транзитивність)

Через ${\displaystyle \mathbb {K} }$ позначимо ${\displaystyle \mathbb {R} }$ або ${\displaystyle \mathbb {C} }$. Нехай ${\displaystyle A\subset \mathbb {K} }$, ${\displaystyle f,g:A\to \mathbb {K} }$ і ${\displaystyle x_{0}}$ — гранична точка множини ${\displaystyle A}$.

Функції ${\displaystyle f}$ і ${\displaystyle g}$ називаються еквівалентними при ${\displaystyle x\to x_{0},}$ якщо ${\displaystyle f-g=o(f),x\to x_{0}.}$

Означення для функцій цілого невід'ємного аргументу аналогічне.

Позначення: ${\displaystyle f(x)\sim g(x),x\to x_{0}}$ або ${\displaystyle f\sim g,x\to x_{0}.}$

1. Відношення ${\displaystyle \sim }$ є відношенням еквівалентності на множині функцій.
2. Нехай для всіх ${\displaystyle x\in A\setminus \{x_{0}\}}$ ${\displaystyle g(x)\neq 0.}$ Тоді ${\displaystyle f\sim g,x\to x_{0}}$ тоді й лише тоді, коли ${\displaystyle \lim \limits _{x\to x_{0}}{\frac {f(x)}{g(x)}}=1.}$
3. Якщо ${\displaystyle f_{1}\sim g_{1},x\to x_{0}}$ і ${\displaystyle f_{2}\sim g_{2},x\to x_{0},}$ то ${\displaystyle f_{1}\cdot f_{2}\sim g_{1}\cdot g_{2},x\to x_{0}.}$
4. Нехай для всіх ${\displaystyle x\in A\setminus \{x_{0}\}\,}$ ${\displaystyle f(x)\neq 0}$, ${\displaystyle g(x)\neq 0}$ і ${\displaystyle f\sim g,x\to x_{0}.}$ Тоді для будь-якої функції ${\displaystyle h:\,A\to \mathbb {K} }$ з існування однієї з границь

випливає існування другої границі і їх рівність.

Аналогічно з існування однієї з границь

випливає існування другої і їх рівність.

Приклад 1: Нехай ${\displaystyle f(x)=2x^{5}-6x^{2}-15}$, ${\displaystyle x\in \mathbb {R} }$ і ${\displaystyle x_{0}=+\infty }$. Маємо:

${\displaystyle {\begin{aligned}|2x^{5}-6x^{2}-15|&\leqslant 2|x^{5}|+6x^{2}+15\\&\leqslant 15|x^{5}|+15|x^{5}|+15|x^{5}|\\&=45|x^{5}|,\end{aligned}}}$

тобто ${\displaystyle L=45}$ і ця нерівність виконується для всіх ${\displaystyle x\in (1,+\infty ).}$

Звідси ${\displaystyle f(x)=O(x^{5}),x\to +\infty .}$

${\displaystyle |2x^{5}-6x^{2}-15|\geqslant 2|x^{5}|}$, тут ${\displaystyle L=2}$ і ${\displaystyle x\in (2.2,+\infty ).}$ Звідси ${\displaystyle f(x)=\Omega (x^{5}),x\to +\infty .}$

Отже, ${\displaystyle f(x)=\Theta (x^{5}),x\to +\infty .}$

Приклад 2: Нехай ${\displaystyle n}$ і ${\displaystyle m}$ цілі числа, ${\displaystyle z\in \mathbb {C} }$. Якщо ${\displaystyle n\geqslant m}$, то ${\displaystyle z^{m}=O(z^{n})}$ при ${\displaystyle z\to \infty }$. Для доведення цього запишемо

Покладемо ${\displaystyle \delta =10}$. Тоді ${\displaystyle |z|>\delta }$ означає що ${\displaystyle |z|^{m-n}\leqslant 10^{m-n}}$, оскільки ${\displaystyle n\geqslant m}$. Отже, якщо ${\displaystyle |z|>10}$, нерівність ${\displaystyle |z|^{m}\leqslant L|z^{m-n}|}$ виконується при виборі ${\displaystyle L=10^{m-n}}$. Також, з аналогічним обмеженням на ${\displaystyle n}$ та ${\displaystyle m}$, ми маємо, що ${\displaystyle z^{n}=O(z^{m})}$ при ${\displaystyle z\to 0}$ з ${\displaystyle \mathbb {C} }$. Для доведення цього запишемо

Виберемо, наприклад, ${\displaystyle \delta =3}$. Тоді, ${\displaystyle 0<|z|<3}$ означає, що ${\displaystyle |z|^{n-m}<3^{n-m}}$ оскільки ${\displaystyle n\geqslant m}$.

Нотація Ландау має дві основні сфери використання:

• У математичному аналізі зазвичай використовується для опису того, наскільки часткова сума ряду наближає задану функцію, наприклад, у формулі Тейлора та асимптотичному розкладі
• В інформатиці використовується для аналізу алгоритмів та їх класифікації

В обох випадках функція ${\displaystyle g(x)}$ в позначеннях, як правило, вибирається максимально простою без константних множників.

Нижче наведений список класів функцій, які часто зустрічаються в аналізі алгоритмів. Тут с — додатна константа, n необмежено зростає. Функції, які зростають повільніше, наведені першими.

Нотація	Назва	Приклад
${\displaystyle \Theta (1)}$	сталий час	Визначенно парності числа (у двійковому запису); Пошук у хеш-таблиці
${\displaystyle \Theta (\log \log n)}$	двічі логарифмічний	Час амортизації на одну операцію при використанні обмеженої черги з пріоритетом[1]
${\displaystyle \Theta (\log n)}$	логарифмічний час	Двійковий пошук; Швидке піднесення до степеня
${\displaystyle \Theta ((\log n)^{c})}$ ${\textstyle c>1}$	полілогарифмічний час
${\displaystyle \Theta (n)}$	лінійний час	Пошук найбільшого або найменшого елементу невпорядкованого масиву
${\displaystyle \Theta (n\log n)=\Theta (\log n!)}$	лінеаритмічний час	Швидке сортування; Сортування злиттям
${\displaystyle \Theta (n^{2})}$	квадратичний час	Сортування бульбашкою; Сортування включенням
${\displaystyle \Theta (n^{c})}$	поліноміальний час	Алгоритм Кармаркара для лінійного програмування; Тест простоти AKS
${\displaystyle \Theta (c^{n})}$ ${\textstyle c>1}$	експоненціальний час	Вирішення задачі комівояжера за допомогою динамічного програмування
${\displaystyle \Theta (n!)}$	факторіальний час	Вирішення задачі комівояжера повним перебором

У інформатиці іноді використовується позначення Õ (читається як м’яке О): f(n) = Õ(g(n)) це скороченням до f(n) = O(g(n) log^k n) для деякого k.^[2] Іноді для цього використовують O^*.^[3] По суті, це нотація великого O, яка ігнорує логарифмічні множники, оскільки на швидкість зростання деякі більші функції від великих вхідних параметрів впливають значно більше, що важливіше для прогнозування поганої продуктивності під час виконання. Це позначення часто використовується, щоб уникнути «придирок» до темпів зростання, які вважаються жорстко обмеженими (log^k n завжди є o(n^ε) для будь-якої константи k і будь-якого ε > 0).

Для позначення функцій, які мають час зростання, що залежить від ${\displaystyle \ln n}$, між поліноміальним та експоненціальним, використовують L-нотацію:

${\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }},}$

де ${\displaystyle c}$ — додатня стала, ${\displaystyle \alpha \in [0,1].}$

Існує декілька узагальнень нотації Ландау для функцій багатьох функцій.^[4][5] Одне з них:

Для функції ${\displaystyle h:\,\mathbb {N} _{0}^{m}\to \mathbb {R} _{+}}$, де ${\displaystyle \mathbb {N} _{0}=\mathbb {N} \cup \{0\}}$, позначимо

Нехай ${\displaystyle f,g:\mathbb {N} _{0}^{m}\to \mathbb {R} _{+}}$. Функція ${\displaystyle f}$ називається підпорядкованою функції ${\displaystyle g}$ якщо існують додатнє дійсне число ${\displaystyle C}$ і натуральне ${\displaystyle n_{0}}$ такі, що для всіх ${\displaystyle n_{1}\geqslant n_{0},\dots ,n_{m}\geqslant n_{0}}$ виконуються нерівності

та

Позначення: ${\displaystyle f(n_{1},\dots ,n_{m})={\hat {O}}(g(n_{1},\dots ,n_{m}))}$ або ${\displaystyle f={\hat {O}}(g)}$.

Аналогічно, ${\displaystyle f(n_{1},\dots ,n_{m})={\hat {\Omega }}(g(n_{1},\dots ,n_{m}))}$, якщо існують додатнє дійсне число ${\displaystyle C}$ і натуральне ${\displaystyle n_{0}}$ такі, що для всіх ${\displaystyle n_{1}\geqslant n_{0},\dots ,n_{m}\geqslant n_{0}}$ виконуються нерівності

та

${\displaystyle f(n_{1},\dots ,n_{m})={\hat {\Theta }}(g(n_{1},\dots ,n_{m}))}$, якщо існують додатні дійсні числа ${\displaystyle C_{1}}$, ${\displaystyle C_{2}}$ і натуральне число ${\displaystyle n_{0}}$ такі, що для всіх ${\displaystyle n_{1}\geqslant n_{0},\dots ,n_{m}\geqslant n_{0}}$ виконуються нерівності

та

Для функцій одного аргументу матимемо, що для ${\displaystyle f(n)\neq 0}$ при деякому ${\displaystyle n\in \mathbb {N} }$ буде ${\displaystyle O(f(n))={\hat {O}}(f(n))}$, ${\displaystyle \Omega (f(n))={\hat {\Omega }}(f(n))}$ і ${\displaystyle \Theta (f(n))={\hat {\Theta }}(f(n)).}$ Однак, для ${\displaystyle f(n)=0}$ при всіх ${\displaystyle n\in \mathbb {N} }$ це не буде вірним.

${\displaystyle f(n_{1},\dots ,n_{m})={\hat {o}}(g(n_{1},\dots ,n_{m}))}$, якщо для кожного додатного дійсного числа ${\displaystyle C}$ існує натуральне число ${\displaystyle n_{0}}$ таке, що для всіх ${\displaystyle n_{1}\geqslant n_{0},\dots ,n_{m}\geqslant n_{0}}$ виконуються нерівності

та

${\displaystyle f(n_{1},\dots ,n_{m})={\hat {\omega }}(g(n_{1},\dots ,n_{m}))}$, якщо для кожного додатного дійсного числа ${\displaystyle C}$ існує натуральне число ${\displaystyle n_{0}}$ таке, що для всіх ${\displaystyle n_{1}\geqslant n_{0},\dots ,n_{m}\geqslant n_{0}}$ виконуються нерівності

та

Для функцій однієї змінної відношення ${\displaystyle {\hat {o}}}$, ${\displaystyle {\hat {\omega }}}$ збігаються з відношеннями ${\displaystyle o}$, ${\displaystyle \omega }$ відповідно.

Додаткова умова до ${\displaystyle {\hat {f}}}$ і ${\displaystyle {\hat {g}}}$ дозволяє зберегти деякі корисні властивості.

1. Для довільного ${\displaystyle C>0}$ буде ${\displaystyle Cf(n_{1},\dots ,n_{m})={\hat {O}}(f(n_{1},\dots ,n_{m})).}$
2. Якщо ${\displaystyle f_{1}={\hat {O}}(g_{1})}$ і ${\displaystyle f_{2}={\hat {O}}(g_{2}),}$ то ${\displaystyle f_{1}+f_{2}={\hat {O}}(\max(g_{1},g_{2})).}$
3. Якщо ${\displaystyle g_{1}}$ не спадає по всім аргументам і ${\displaystyle g_{1}(n_{1},\dots ,n_{m})\leqslant g_{2}(n_{1},\dots ,n_{m})}$ при ${\displaystyle n_{1}\geqslant n_{0},\dots ,n_{m}\geqslant n_{0}}$ для деякого ${\displaystyle n_{0}\in \mathbb {N} ,}$ то з того, що ${\displaystyle f={\hat {O}}(g_{1})}$ випливає, що ${\displaystyle f={\hat {O}}(g_{2}).}$
4. Якщо ${\displaystyle g_{1}}$ та ${\displaystyle g_{2}}$ не спадають по всім аргументам, то з того, що ${\displaystyle f_{1}={\hat {O}}(g_{1})}$ та ${\displaystyle f_{2}={\hat {O}}(g_{2})}$ випливає, що ${\displaystyle f_{1}\cdot f_{2}={\hat {O}}(g_{1}\cdot g_{2}).}$

• Таблиця математичних символів
• Основна теорема про рекурентні співідношення
• Обчислювальна складність

• Дороговцев А. Я. Математичний аналіз. Частина 1. — К. : Либідь, 1993. — 320 с. — ISBN 5-325-00380-1.(укр.)
• Григорій Михайлович Фіхтенгольц. Курс диференціального та інтегрального числення. — 2024. — 2403 с.(укр.)
• John M. Howie. Complex Analysis. — Springer London, 2003. — 260 с. — ISBN 978-1-4471-0027-0. — DOI:https://doi.org/10.1007/978-1-4471-0027-0.
• Hardy, G. H. (1910). Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond. Cambridge University Press.
• Knuth, Donald (1997). Fundamental Algorithms. The Art of Computer Programming. Т. 1 (вид. 3-тє). Addison-Wesley. ISBN 978-0-201-89683-1.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (вид. 2-ге). MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3.
• Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. с. 226–228. ISBN 978-0-534-94728-6.