aboutsummaryrefslogtreecommitdiff
path: root/Practical2/report/analysis.tex
diff options
context:
space:
mode:
authorCamil Staps2015-12-15 19:53:30 +0000
committerCamil Staps2015-12-15 19:53:30 +0000
commit126288502f64e1959e82bcab21c107f7fbee8f68 (patch)
tree6d759b8cffb8dd3dfd067f60f573507f15ecc3d4 /Practical2/report/analysis.tex
parentFinish first version report practical 2 (diff)
Finish report practical 2HEADmaster
Diffstat (limited to 'Practical2/report/analysis.tex')
-rw-r--r--Practical2/report/analysis.tex4
1 files changed, 2 insertions, 2 deletions
diff --git a/Practical2/report/analysis.tex b/Practical2/report/analysis.tex
index d989fe6..ac5d6a9 100644
--- a/Practical2/report/analysis.tex
+++ b/Practical2/report/analysis.tex
@@ -1,11 +1,11 @@
\section{Complexity analysis}
\label{sec:analysis}
-We iterate $p$ in $\pazocal O(|\bar a'|) = \pazocal O(|\bar a|)$. In every iteration we do two things:
+We iterate over $p$ in $\pazocal O(|\langle a_i\in\bar a\mid 5\nmid a_i\rangle|) = \pazocal O(|\bar a|)$. In every iteration we do two things:
\begin{itemize}
\item We build $S$ in $\pazocal O(p)=\pazocal O(|\bar a|)$.
- \item We iterate $d$ in $\pazocal O(k)$. Apart from the special cases that $p=0$ or $d=0$, we then have to iterate over $i$ in $\pazocal O(p)=\pazocal O(|\bar a|)$.
+ \item We iterate over $d$ in $\pazocal O(k)$. Apart from the special cases that $p=0$ or $d=0$, we then have to iterate over $i$ in $\pazocal O(p)=\pazocal O(|\bar a|)$.
The computations in this last loop take constant time: $\PR$ can be implemented in constant time as has been seen in \autoref{sec:implementation}, and computing the maximum can be done while iterating over $i$.
\end{itemize}