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|)$.
|
