diff options
Diffstat (limited to 'Practical2/report/analysis.tex')
| -rw-r--r-- | Practical2/report/analysis.tex | 4 |
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} |