1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
\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 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 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<n\}$). For the rest, all operations take constant time, giving a worst case time of $c_1\cdot n+c_2$ for some constants $c_1,c_2$.
\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
\end{enumerate}
\end{document}
|
