aboutsummaryrefslogtreecommitdiff
path: root/Practical2/report/analysis.tex
blob: ac5d6a993d75516b63006726b95be0b7034873b8 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
\section{Complexity analysis}
\label{sec:analysis}

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 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}

This gives a total time complexity of $\pazocal O(k\cdot|\bar a|^2)$.

\medskip

The algorithm uses a two-dimensional array $G$ to store solutions to subproblems. This array uses $\pazocal O(k\cdot|\bar a|)$ space. The auxiliary array $S$ takes only linear space in $|\bar a|$ and can therefore be ignored in the overall space complexity. This gives the algorithm a space complexity of $\pazocal O(k\cdot|\bar a|)$.