From 3875ac2b8df9145a66e9f6fcf34e77eb3bc2d072 Mon Sep 17 00:00:00 2001
From: Nunigan <michael.schmid2@ost.ch>
Date: Tue, 27 Jul 2021 22:01:05 +0200
Subject: added first part of paper and code

---
 .../multiplikation/presentation/slides/bigO.tex    | 251 +++++++++++++++++++++
 1 file changed, 251 insertions(+)
 create mode 100644 buch/papers/multiplikation/presentation/slides/bigO.tex

(limited to 'buch/papers/multiplikation/presentation/slides/bigO.tex')

diff --git a/buch/papers/multiplikation/presentation/slides/bigO.tex b/buch/papers/multiplikation/presentation/slides/bigO.tex
new file mode 100644
index 0000000..d425da8
--- /dev/null
+++ b/buch/papers/multiplikation/presentation/slides/bigO.tex
@@ -0,0 +1,251 @@
+
+\begin{frame}
+  \frametitle{Big $\mathcal{O}$ notation}
+\begin{itemize}
+  \item <1-> Time complexity of an algorithm
+  \item <2-> How many multiplications in a function
+  \item <3-> Drop Constants
+\end{itemize}
+\end{frame}
+
+
+\begin{frame}
+  \frametitle{Big $\mathcal{O}$ notation}
+  \onslide<1->{
+
+  \begin{algorithm}[H]\caption{Foo 1}
+    \setlength{\lineskip}{7pt}
+    \begin{algorithmic}[1]
+      \Function{foo}{$a, b$}
+        \State \textbf{return} $a+b$
+     \EndFunction
+    \end{algorithmic}
+  \end{algorithm}
+}
+\onslide<2->{
+$\mathcal{O}(1)$
+  }
+\end{frame}
+
+\begin{frame}
+  \frametitle{Big $\mathcal{O}$ notation}
+  \onslide<1->{
+
+  \begin{algorithm}[H]\caption{Foo 2}
+    \setlength{\lineskip}{7pt}
+    \begin{algorithmic}[1]
+      \Function{foo}{$a, b$}
+        \State $ x \gets a+b $
+        \State $ y \gets a \cdot b $
+        \State \textbf{return} $x+y$
+     \EndFunction
+    \end{algorithmic}
+  \end{algorithm}
+}
+\onslide<2->{
+$\mathcal{O}(1) + \mathcal{O}(1) = 2\mathcal{O}(1) = \mathcal{O}(1) $
+  }
+\end{frame}
+
+\begin{frame}
+  \frametitle{Big $\mathcal{O}$ notation}
+  \onslide<1->{
+
+  \begin{algorithm}[H]\caption{Foo 3}
+    \setlength{\lineskip}{7pt}
+    \begin{algorithmic}[1]
+      \Function{foo}{$\mathbf{A}, \mathbf{B}$,n}
+      \State $ sum \gets 0$
+      \For{$i = 0,1,2 \dots,n$}
+        \State $ sum \gets sum + A[i] \cdot B[i] $
+        \EndFor
+
+        \State \textbf{return} $sum$
+
+     \EndFunction
+    \end{algorithmic}
+  \end{algorithm}
+}
+\onslide<2->{
+$\mathcal{O}(n)$
+  }
+\end{frame}
+
+\begin{frame}
+  \frametitle{Big $\mathcal{O}$ notation}
+  \onslide<1->{
+
+  \begin{algorithm}[H]\caption{Foo 4}
+    \setlength{\lineskip}{7pt}
+    \begin{algorithmic}[1]
+      \Function{foo}{$\mathbf{A}, \mathbf{B}$,n}
+      \State $ sum \gets 0$
+      \For{$i = 0,1,2 \dots,n$}
+      \For{$j = 0,1,2 \dots,n$}
+      \State $ sum \gets sum + A[i] \cdot B[j] $
+      \EndFor
+      \EndFor
+        \State \textbf{return} $sum$
+     \EndFunction
+    \end{algorithmic}
+  \end{algorithm}
+}
+\onslide<2->{
+$\mathcal{O}(n^2)$
+  }
+\end{frame}
+
+% \begin{frame}
+%   \frametitle{Big $\mathcal{O}$ notation}
+%   \onslide<1->{
+%
+%   \begin{algorithm}[H]\caption{Fibonacci}
+%     \setlength{\lineskip}{7pt}
+%     \begin{algorithmic}[1]
+%       \Function{fib}{$n$}
+%       \If{$n <= 1$}
+%       \State \textbf{return} $1$
+%       \Else
+%         \State \textbf{return} fib($n-1$) + fib($n-2$)
+%         \EndIf
+%
+%      \EndFunction
+%     \end{algorithmic}
+%   \end{algorithm}
+% }
+% \onslide<2->{
+% \[
+% \langle x,y \rangle =
+% \begin{cases}
+%  \displaystyle $\mathcal{O}(1)$  & \text{if  $n \leq 2$}\\
+% \displaystyle $ 2 \mathcal{T}(\frac{n}{2})$  & \text{if  $n > 2$}
+% \end{cases}
+% \]  }
+% \end{frame}
+
+
+\begin{frame}
+  \frametitle{Big $\mathcal{O}$ notation}
+\begin{tikzpicture}
+\begin{axis}[
+    axis lines = left,
+    xlabel = $n$ (Data Input),
+    ylabel = {$t$ (time)},
+    legend pos=north east,
+    very thick,
+    ymax = 20,
+    yticklabels=\empty,
+    xticklabels=\empty,
+    scale only axis=true,
+  width=12cm, height=6cm,
+    ]
+%Below the red parabola is defined
+\addplot [
+    domain= 1:6,
+    samples=100,
+    color=red,
+]
+{1};
+\addlegendentry{$\mathcal{O}(1)$}
+%Here the blue parabloa is defined
+\addplot [
+    domain= 1:6,
+    samples=100,
+    color=green,
+]
+{x};
+\addlegendentry{$\mathcal{O}(n)$}
+\addplot [
+    domain= 1:6,
+    samples=100,
+    color=blue,
+]
+{x^2};
+\addlegendentry{$\mathcal{O}(n^2)$}
+\addplot [
+    domain= 1:6,
+    samples=100,
+    color=purple,
+]
+{x^3};
+\addlegendentry{$\mathcal{O}(n^3)$}
+\addplot [
+    domain= 1:3,
+    samples=100,
+    color=black,
+]
+{exp(x)};
+\addlegendentry{$\mathcal{O}(e^n)$}
+\addplot [
+    domain= 1:6,
+    samples=100,
+    color=orange,
+]
+{log2(x)};
+\addlegendentry{$\mathcal{O}(\log n)$}
+\end{axis}
+\end{tikzpicture}
+
+\end{frame}
+
+\begin{frame}
+  \frametitle{Big $\mathcal{O}$ notation}
+\begin{tikzpicture}
+\begin{axis}[
+    axis lines = left,
+    xlabel = $n$ (Data Input),
+    ylabel = {$t$ (time)},
+    legend pos=north east,
+    very thick,
+    ymax = 500,
+    yticklabels=\empty,
+    xticklabels=\empty,
+    scale only axis=true,
+  width=12cm, height=6cm,
+    ]
+\addplot [
+    domain= 1:20,
+    samples=100,
+    color=red,
+]
+{1};
+\addlegendentry{$\mathcal{O}(1)$}
+\addplot [
+    domain= 1:20,
+    samples=100,
+    color=green,
+]
+{x};
+\addlegendentry{$\mathcal{O}(n)$}
+\addplot [
+    domain= 1:20,
+    samples=100,
+    color=blue,
+]
+{x^2};
+\addlegendentry{$\mathcal{O}(n^2)$}
+\addplot [
+    domain= 1:10,
+    samples=100,
+    color=purple,
+]
+{x^3};
+\addlegendentry{$\mathcal{O}(n^3)$}
+\addplot [
+    domain= 1:10,
+    samples=100,
+    color=black,
+]
+{exp(x)};
+\addlegendentry{$\mathcal{O}(e^n)$}
+\addplot [
+    domain= 1:20,
+    samples=100,
+    color=orange,
+]
+{log2(x)};
+\addlegendentry{$\mathcal{O}(\log n)$}
+\end{axis}
+\end{tikzpicture}
+
+\end{frame}
-- 
cgit v1.2.1