this is for holding javascript data
Niclas Alexandersson edited Complexity analysis.tex
about 10 years ago
Commit id: e20f318dbd7cf30d4bd08d4c57f9c93af8ec7842
deletions | additions
diff --git a/Complexity analysis.tex b/Complexity analysis.tex
index 7001eb3..08ac8c6 100644
--- a/Complexity analysis.tex
+++ b/Complexity analysis.tex
...
T(n) = R(n) + k_0 + k_1 n + k_2 n \log n
\]
This means that if, $R(n) \in O(n \log n)$, then $T(n) \in O(n \log n)$ as well. If not, then $T(n) \in O(R(n))$. Thus, if we can find $R$ in $O(n \log n)$, then our solution is $O(n \log n)$. For b), where $R$ is chosen arbitrarily, it can trivially be seen that $R(n) \in O(1)$. For a), the case is a bit more complex, but it should be possible to achieve by creating two lists containing all the intervals, sorting one by starting angle and one by ending angle, and then going through the lists in parallell, which would make $R(n) \approx 2n
log \log n + 2n$, meaning $R(n) \in n
log \log n$.