\documentclass[10pt,a4paper]{article} \usepackage[margin=2cm]{geometry} \usepackage{enumitem} \setenumerate[1]{label=1.\arabic*.} \setenumerate[2]{label=\textit{\alph*})} % textcomp package is not available everywhere, and we only need the Copyright symbol % taken from http://tex.stackexchange.com/a/1677/23992 \DeclareTextCommandDefault{\textregistered}{\textcircled{\check@mathfonts\fontsize\sf@size\z@\math@fontsfalse\selectfont R}} \usepackage{fancyhdr} \renewcommand{\headrulewidth}{0pt} \renewcommand{\footrulewidth}{0pt} \fancyhead{} \fancyfoot[C]{Copyright {\textcopyright} 2015 Camil Staps} \pagestyle{fancy} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n} \parindent0pt \title{Algoritmen en Datastructuren - assignment 1} \author{Camil Staps\\\small{s4498062}} \begin{document} \maketitle \thispagestyle{fancy} \begin{enumerate} \item Essentially we need to equate these expressions to $60\cdot10^6$ and solve for $n$. \begin{enumerate} \item $n^2 = 60 \cdot 10^6$; $n = \sqrt{60 \cdot 10^6} \approx 7745.97$. \item $n\log n = 60 \cdot 10^6$; $n \approx 8.65 \cdot 10^6$.\footnote{Assuming the base 10 logarithm.} \item $2^n = 60 \cdot 10^6$; $n = \log_2(60\cdot10^6) \approx 25.84$. \item $n\sqrt n = 60 \cdot 10^6$; $n = \left(60\cdot10^6\right)^{\frac23} \approx 153261.89$. \item $n^{100} = 60 \cdot 10^6$; $n = \sqrt[100]{60\cdot10^6} \approx 1.20$. \item $4^n = 60 \cdot 10^6$; $n = \log_4(60\cdot10^6) \approx 12.92$. \item $n = 60 \cdot 10^6$. \end{enumerate} \item \begin{enumerate} \item Yes. \item Yes. \item No. \item No. \item Yes. \item Yes. \item No. \item No. \item No. \item Yes. \item No. \end{enumerate} \item \begin{enumerate} \item \begin{enumerate}[label=\textit{\alph*})] \item Take $c=10,n_0=1$. For $n\geq n_0 = 1$ we know $9n\geq9>1$, therefore $cn = 10n > n + 1$ for all $n\geq n_0$ and thus $n+1 \in \pazocal{O}(n)$. \item Take $c=3,n_0=0$. Then $3n>2n$ for all $n\geq n_0$, therefore $2n \in \pazocal{O}(n)$. \end{enumerate} \item We take $c=1,n_0=1$. Claim: $\forall_{n\geq n_0=1}\left[n < c\cdot2^n = 2^n\right]$. \begin{proof} We prove this with induction over $n$. \textbf{Base case}: Let $n=1$, then $n = 1 < 2 = 2^1 = 2^n$. \textbf{Inductive step}: assume that the claim holds for a certain $n=k\geq n_0=1$ (inductive hypothesis). Now, we know $k+1 - k = 1 < 2^k = 2^{k+1} - 2^k$. Therefore, also $k+1 < 2^{k+1}$, i.e. the claim holds for $k+1$ as well. From the principle of induction it now follows that $\forall_{n\geq n_0=1}\left[n < c\cdot2^n = 2^n\right]$. \end{proof} \end{enumerate} \item I'm assuming constant time for basic instructions (declaration, comparison, logical operations, branches , function calls and returns, arithmetic instructions). \begin{enumerate} \item In this case \texttt{v[i] == x} is never true, meaning we execute the \texttt{while} loop as long as possible (that is, for $i\in\{k\in\mathbb{N}\mid k 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}