diff options
| -rw-r--r-- | assignment1.tex | 85 |
1 files changed, 85 insertions, 0 deletions
diff --git a/assignment1.tex b/assignment1.tex new file mode 100644 index 0000000..ea0151e --- /dev/null +++ b/assignment1.tex @@ -0,0 +1,85 @@ +\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 %Todo + \item Yes. + \item Yes. + \item No. + \item Yes. + \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 %Todo + + \item %Todo +\end{enumerate} + +\end{document} + |