diff options
Diffstat (limited to 'assignment1.tex')
| -rw-r--r-- | assignment1.tex | 9 |
1 files changed, 7 insertions, 2 deletions
diff --git a/assignment1.tex b/assignment1.tex index ea0151e..ebda083 100644 --- a/assignment1.tex +++ b/assignment1.tex @@ -49,7 +49,7 @@ \item Yes. \item Yes. \item No. - \item %Todo + \item No. \item Yes. \item Yes. \item No. @@ -76,7 +76,12 @@ \end{proof} \end{enumerate} - \item %Todo + \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} |