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