this is for holding javascript data
Francesco Romeo added section_Order_Notation_and_Complexity__.tex
about 8 years ago
Commit id: 53363c64722ac00fc9a390deda4b107ad2b8f593
deletions | additions
diff --git a/section_Order_Notation_and_Complexity__.tex b/section_Order_Notation_and_Complexity__.tex
new file mode 100644
index 0000000..2e2d567
--- /dev/null
+++ b/section_Order_Notation_and_Complexity__.tex
...
\section*{Order Notation and Complexity}
In Chapter 0 we showed the number of steps required e.g. by the Euclidean Algorithm or the Fast Powering Algorithm.
This computation is very important when we want to know how much time an algorithm requires to find solution at a problem and it's necessary to introduce the \textbf{Order Notation}.
\begin{defn}[Order Notation]
Let $f(x)$ and $ g(x)$ be functions, then we will say that $f(x)=\mathcal{O}(g(x))$ if there are positive constants $c$ and $C$ such that
$$f(x) \leq cg(x) \ \ \ \ \ \ \forall x \geq C$$
\end{defn}
and it will result that
$$\lim_{x \to +\infty} \dfrac{f(x)}{g(x)}= c \in \mathbb{R} $$
In the cryptographical algorithms the arguments are integers and we could call them $k$.
We distinguish some types of complexity times:
\begin{itemize}
\item \textbf{Polynomial Time}: when the algorithm takes $\mathcal{O}(k^{A})$ steps with $A \geq 0$.
\item\textbf{Subexponential Time}: if $\forall \varepsilon > 0 $ the algoritmh takes $\mathcal{O}_{\varepsilon}(e^{\varepsilon k})$ steps.
\item \textbf{Exponential Time}: if $\exists c > 0 $ such that the algoritmh takes $\mathcal{O}(e^{ck})$ steps.
\end{itemize}
It's easy to verify that Polynomial Time $\Rightarrow$ Subexponential Time $\Rightarrow$ Exponential Time.
