Xavier Holt edited We_take_textbf_Step_1__.tex  about 8 years ago

Commit id: ea7c36d8a6daa9055fb9982cab35369d66338cee

deletions | additions      

       

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