\Section{Асимптотика}{7 сентября}{Сергей Копелиович}

\Subsection{$\O$-обозначния}

\begin{Def}{$f = \O(g)$} \quad
  $\exists N > 0, C > 0 \colon \forall n \ge N, f(n) \le C \cdot g(n)$
\end{Def}

\begin{Def}{$f = \Omega(g)$} \quad
  $\exists N > 0, C > 0 \colon \forall n \ge N, f(n) \ge C \cdot g(n)$
\end{Def}

\begin{Def}{$f = o(g)$} \quad
  $\forall C > 0 \exists N > 0 \colon \forall n \ge N, f(n) \le C \cdot g(n)$
\end{Def}

\begin{Def}{$f = \omega(g)$} \quad
  $\forall C > 0 \exists N > 0 \colon \forall n \ge N, f(n) \ge C \cdot g(n)$
\end{Def}

\begin{Def}{$f = \Theta(g)$} \quad
  $\exists N > 0, C_1 > 0, C_2 > 0 \colon \forall n \ge N, C_1 \cdot g(n) \le f(n) \le C_2 \cdot g(n)$
\end{Def}

\begin{Rem}$f = \Theta(g) \EQ g = \Theta(f)$\end{Rem}
\begin{Rem}$f = \O(g), g = \O(f) \EQ f = \Theta(g)$\end{Rem}
\begin{Rem}$f = \Omega(g) \EQ g = \O(f)$\end{Rem}
\begin{Rem}$f = \omega(g) \EQ g = o(f)$\end{Rem}
\begin{Rem}$f = \O(g), g = \O(h) \SO f = \O(h)$\end{Rem}
\begin{Rem}{Обобщение:} $\forall \beta \in \{\O, o, \Theta, \Omega, \omega\} \colon f = \beta(g), g = \beta(h) \SO f = \beta(h)$\end{Rem}

\Subsection{Суммы и интегралы}

\begin{Lm}\label{Lm:easyint} $\forall f(x) \nearrow [a..a{+}1] \colon f(a) \le \int_{a}^{a{+}1}f(x)dx \le f(a{+}1)$\end{Lm}

\begin{Lm}\label{Lm:int1} $\forall f(x) \nearrow [a..b] \sum\limits_{i=a}^b f(i) \le \int\limits_{a}^{b{+}1}f(x)dx$\end{Lm}
\begin{proof} Сложили неравенства из \autoref{Lm:easyint} \end{proof}

\begin{Lm}\label{Lm:int2} $\forall f(x) \nearrow [a..b], f > 0 \int\limits_{a}^{b}f(x)dx \le \sum\limits_{i=a}^b f(i)$\end{Lm}
\begin{proof} Сложили неравенства из \autoref{Lm:easyint}, выкинули $[a{-}1,a]$ из интеграла. \end{proof}

\begin{Lm}$\forall f(x) \nearrow [a..b] \int\limits_{a}^{b{+}1}f(x)dx - \sum\limits_{i=a}^b f(i) \le f(b{+}1) - f(a)$\end{Lm}

\begin{Thm}{Замена суммы на интеграл} \\
$\forall f(x) \nearrow [1..\infty), f > 0, S(n) = \sum\limits_{i=1}^n f(i), I_1(n) = \int\limits_1^{n}, I_2(n) = \int\limits_1^{n{+}1}, 
I_1(n) = \Theta(I_2(n)) {\bf\SO} S(n) = \Theta(I_1(n))$
\end{Thm}
\begin{proof}
Из лемм \autoref{Lm:int1} и \autoref{Lm:int2} имеем $I_1(n) \le S(n) \le I_2(n)$. \\
$C_1 I_1(n) \le I_2(n) \le C_2 I_1(n) \SO \min(C_1, 1) I_1(n) \le S(n) \le C_2 I_1(n)$
\end{proof}