this is for holding javascript data
Niclas Alexandersson edited Complexity analysis.tex
about 10 years ago
Commit id: 69b390c51d5dd714d81dc55442003c2de0b6f5ab
deletions | additions
diff --git a/Complexity analysis.tex b/Complexity analysis.tex
index e1118cc..0fdf132 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
$O(n \log n)$ 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 n + 2n$, meaning $R(n) \in n \log n$.