\subsection{Asymptotics}

\label{s:asymptotics}
Here we recall briefly some facts and notations concerning 
asymptotic behaviour of functions and series.
For a more detailed exposition we suggest \cite{Graham:1994}.

\tinysection{Asymptotic notations.}
For positive functions $f(n)$ and $g(n)$, we make use of these
notations for asymptotic behaviour:
\begin{align}
f(n) \sim g(n) ~~ & \Longleftrightarrow ~~ \lim_{n \rightarrow \infty} \frac{f(n
)}{g(n)}=1 \\
f(n) \prec g(n) ~~ & \Longleftrightarrow ~~ \lim_{n \rightarrow \infty} \frac{f(n)}{g(n)}=0 \\
f(n) \preceq g(n) ~~ & \Longleftrightarrow ~~ \exists c \in \R ~.~ \lim_{n \rightarrow \infty} \frac{f(n)}{g(n)}=c 
\end{align}
The ``big-O'' style of
notation $f \in o(g)$ is equivalent to $f(n) \prec g(n)$.
When we write $h(n) \sim g(n) + o(n^2)$ we mean
there exists some function $f \in o(n^2)$ such that
$h(n) \sim g(n) + f(n)$.

\tinysection{Series and their convergence.}
A series $\sum_{i=1}^\infty a_i$ is convergent when
$\lim_{N \rightarrow \infty} \sum_{i=1}^N a_i$ exists
in the standard reals; otherwise it is divergent.
The Harmonic series $h_n = \frac{1}{n}$ is divergent,
since $\sum_{i=0}^\infty h_i = 1 + \frac{1}{2} + \frac{1}{3} + \cdots$
fails to converge.

We shall make use of the following key fact for bounding convergent
sequences.
\begin{fact}
\label{fact:seqbound}
Let $a_n,b_n$ be positive sequences.
If $\sum_{n=1}^\infty a_n$ converges and $\sum_{n=1}^\infty b_n$
diverges, then $a_n \prec b_n$.
\end{fact}
\refprop{fact:seqbound} is useful to establish a bound on the asymptotic
growth of a sequence: for example, if $\sum_{n=1}^\infty a_n$ must converge, 
then $a_n \prec \frac{1}{n}$ since the harmonic series diverges.

