Xavier Holt edited begin_claim_The_algorithm_runs__.tex  about 8 years ago

Commit id: bc2f345519775c0d5388e9d4ff3ea593ddfc8f7a

deletions | additions      

       

&= 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 \tag{with  $C\geq0$}\\ &= O(n\log n) + \left(n\log n - C \right) &&\tag{inner \tag{inner  bracket $\geq 0$}\\ &\leq O(n\log n) + O(n\log n)\\  &\in O(n\log n)  \end{align*}