Xavier Holt edited We_take_textbf_Step_1__.tex  about 8 years ago

Commit id: 4a06ec702702768948db52a9b3948225fd505b88

deletions | additions      

       

\end{itemize}  Putting this all together, the running time of our recursive algorithm given an input size $n$ is $R\left(n\right) := =  O\left(n\right) + 2R\left(\frac{n}{2}\right)$. \begin{claim}  $R\left(n\right)$ runs in $O\left(n\log n\right)$