Niclas Alexandersson edited Complexity analysis.tex  about 10 years ago

Commit id: 0e755d09661300a3dd2b2562b6a78c3d48585f48

deletions | additions      

       

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