\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:

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