diff options
Diffstat (limited to 'assignment1.tex')
| -rw-r--r-- | assignment1.tex | 14 |
1 files changed, 13 insertions, 1 deletions
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} |