Mazdak Farrokhzad edited stuff.tex  about 10 years ago

Commit id: 026fffbf09f5565ec8690e33989373a2e3e36069

deletions | additions      

       

\begin{equation}  \begin{split}  m &= \sqrt{n}\\  f(n) T(n)  &= a + \sum_{p = 2}^{m}\left[b + \sum_{i = 1}^{\frac{n}{p}} c\right]\\ &= a + \sum_{p = 2}^{m}b + \sum_{p = 2}^{m}\left[c\sum_{i = 1}^{\frac{n}{p}} 1\right]\\  &= a + b\sum_{p = 2}^{m}1 + c\sum_{p = 2}^{m}\left[\sum_{i = 1}^{\frac{n}{p}}\right]\\  &= a + b(m - 1) + c\sum_{p=2}^{m}\frac{n}{p}\\ 

\end{equation}  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}))  \end{document}