Mazdak Farrokhzad edited solving-the-sum.tex  about 10 years ago

Commit id: 83452306289e0a13fe23bc2f334c675d8dd73b87

deletions | additions      

       

We know that $H_x$ oscillates around $ln(x)$, and that $H_x \in \mathcal{O}(log(n))$\\  Thus: \[T(n) \in \mathcal{O}(nlog(\sqrt{n}))\]  We use the logarithm identity $log_b(x^d) = dlog_b(x)$ to simplify and yield:  \[T(n) \in \mathcal{O}(nlog(n))\]\end{document}