From 52a67a6466a4bc10f809f1fb68e2db5830c05f64 Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Fri, 11 Dec 2015 13:19:52 +0000
Subject: Finish first version report practical 2

Some changes were made to the code and the Makefile to clean up, make it
more in line with the algorithm as described in the report, etc. No
significant changes.
---
 Practical2/report/analysis.tex | 18 ++++++++++++++++++
 1 file changed, 18 insertions(+)
 create mode 100644 Practical2/report/analysis.tex

(limited to 'Practical2/report/analysis.tex')

diff --git a/Practical2/report/analysis.tex b/Practical2/report/analysis.tex
new file mode 100644
index 0000000..d989fe6
--- /dev/null
+++ b/Practical2/report/analysis.tex
@@ -0,0 +1,18 @@
+\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|)$.
+
-- 
cgit v1.2.3