From d71da7673c32d03ef1e5a315244d3e438b2cdc99 Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Sat, 5 Sep 2015 17:05:42 +0200
Subject: 1.6

---
 assignment1.tex | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

(limited to 'assignment1.tex')

diff --git a/assignment1.tex b/assignment1.tex
index ebda083..0b1427e 100644
--- a/assignment1.tex
+++ b/assignment1.tex
@@ -83,7 +83,19 @@
             \item In this case \texttt{v[i] == x} for $i=0$, meaning we loop the \texttt{while} loop exactly once, giving it a constant time like all other operations. This gives us best case time $c$ for some constant $c$.
         \end{enumerate}
 
-    \item %Todo
+    \item I'm making assumptions similar to the ones I made for 1.4.
+
+        \begin{enumerate}
+            \item In any case we need $\frac{n(n+1)}{2}\cdot c$ operations for the \texttt{for} loops for some constant $c$; the content of \texttt{v} does not have any influence on this. Then in the best case the condition \texttt{v[i] > v[i+1]} is always false, so that we don't need to \texttt{swap}. This would give us $\frac{n(n+1)}{2}\cdot c$ operations in total for some constant $c$.
+            \item In this case we need to \texttt{swap} in every iteration of the inner \texttt{for} loop in every iteration of the outer \texttt{for} loop, giving $\frac{n(n+1)}{2}\cdot c'$ \texttt{swap} operations in addition to the $\frac{n(n+1)}{c}$ operations for the \texttt{for} loops, for some constant $c'$. This gives $\frac{n(n+1)}{2}\cdot c\cdot c'$ operations in total for some constants $c,c'$. This is, of course, assuming \texttt{swap} takes constant time.
+            \item We could let the algorithm recognise when it's done. That is, before the inner \texttt{for} loop set some \texttt{bool done = false}. Then, in the \texttt{if} branch set that boolean to \texttt{true}. The outer \texttt{for} loop need only continue if \texttt{e > 0 \&\& !done}.
+        \end{enumerate}
+
+    \item No, this is not always true. 
+        
+        \begin{proof}
+            Take for example $f(n)=n\bmod{2}$. Now assume that $f(n) \in \pazocal{O}(f(n+1))$. This means, by definition, that there are $c\in\mathbb{R},n_0\in\mathbb{N}$ s.t. for all $n\in\mathbb{N},n>n_0$ it holds that $f(n)\leq c\cdot f(n+1)$. Then let's look at the smallest $n>n_0$ for which $2\not\div n$. Obviously, $f(n)=1$ and $f(n+1)=0$. There is no $c\in\mathbb{R}$ s.t. $1\leq c\cdot0$, therefore, there is no $c\in\mathbb{R}$ s.t. $f(n)\leq c\cdot f(n+1)$. But this is in contradiction with our assumption that there are $c\in\mathbb{R},n_0\in\mathbb{N}$ s.t. for all $n\in\mathbb{N},n>n_0$ it holds that $f(n)\leq c\cdot f(n+1)$. Hence, it is not true for every $f:\mathbb{N}\to\mathbb{N}$ that $f(n)\in\pazocal{O}(f(n+1))$.
+        \end{proof}
 \end{enumerate}
 
 \end{document}
-- 
cgit v1.2.3

