Niclas Alexandersson edited solving the sum.tex  about 10 years ago

Commit id: 8be8551382e156782a26f1d8d0be287e17f5d534

deletions | additions      

       

We know that $H_n$ is bounded from above by a constant multiple of $\log(n)$, meaning $H_n \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: simplify, which gives us:  \[T(n) \in \mathcal{O}(nlog(n))\]