Xavier Holt edited begin_claim_The_algorithm_runs__.tex  about 8 years ago

Commit id: dbd8ce9fa6ad76c9588be19d1b9f36fb5e489ea6

deletions | additions      

       

&= O\left(n\log n\right) + n^{\log_2 2}O\left(1\right) + \sum_{j=0}^{\log_2 n-1} 2^j O\left(\log n - \log{2^j}\right)\\   &= O\left(n\log n\right) + O\left(n\right) + \left(O\left(\log n\right)\sum_{j=0}^{\log_2 n-1} 2^j - \sum_{j=0}^{\log_2 n-1} O\left(2^j\log{2^j} \right)\right)\\   &=O\left(n\log n\right) + O\left(n\right) + \left(O\left(\log n\right) 2^{\log_2 n} - C\right) \tag{with $C\geq0$}\\   &= O\left(n\log n\right) + O\left(n\right) +  O\left(n\log n\right) - C\\ &\leq &\geq  O\left(n\log n\right) + O\left(n\right) +  O\left(n\log n\right)\\ &\in O\left(n\log n\right)  \end{align*}