deletions | additions       diff --git a/begin_claim_The_algorithm_runs__.tex b/begin_claim_The_algorithm_runs__.tex  index ec542cb..a49e525 100644  --- a/begin_claim_The_algorithm_runs__.tex  +++ b/begin_claim_The_algorithm_runs__.tex 
...
\begin{claim}  The algorithm runs in $O(m\log^2m)$ $O(n\log n)$  \end{claim}  \begin{proof}  Assume.  \begin{align*} R(n) &= 2R(n/2) + O(\log n) + O(n) \\ &=2\left(2R(n/4) + O(\log n/2) + O(n/2)\right) + O(\log n) + O(n)\\ &= iO(n) + \sum_{j=0}^{i-1} 2^j O(\log \frac{n}{2^i}) + 2^iR(\frac{n}{2^i})\\ &= O(n\log n) + \sum_{j=0}^{\log n-1} 2^j O(\log \frac{n}{2^i}) + 2^{\log n}R(1)\\ &= O(n\log n) + n^{\log 2}O(1) + \sum_{j=0}^{\log n-1} 2^j (\log n - \log{2^j})\\ &= O(n\log n) + O(n) + \left(\log n\sum_{j=0}^{\log n-1} 2^j - \sum_{j=0}^{\log n-1} 2^j\log{2^j} \right)\\ &= O(n\log n) + \left(\log n \times 2^{\log n} - C \right) &\text{with $C\geq0$}\\ &= O(n\log n) + \left(n\log n - C \right) &\text{inner bracket $\geq 0$}\\ &\leq O(n\log n) + O(n\log n)\\  &\in O(n\log n)  \end{align*} \end{proof}