Xavier Holt edited begin_claim_The_algorithm_runs__.tex  about 8 years ago

Commit id: f7022575938c010877338a94be3698d64fab270d

deletions | additions      

       

&= 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{the term inside the &\text{inner  bracket must be $>0$ as it was a sum of $\log$ values} $\geq 0$}  \\ \end{align*}  \end{proof}