this is for holding javascript data
Mazdak Farrokhzad deleted file solving-the-sum.tex
about 10 years ago
Commit id: 473b2f58c5ee8fdc5306f31733bd104d3cd63c13
deletions | additions
diff --git a/solving-the-sum.tex b/solving-the-sum.tex
deleted file mode 100644
index 000ad61..0000000
--- a/solving-the-sum.tex
+++ /dev/null
...
\section{Solving the sum}
\subsection{Laws and forumulas of summation}
These summation laws/formulas are used frequently.
They are very common and thus we won't prove any of them.
Most of them can be found \href{http://en.wikipedia.org/wiki/Summation}{here}
\begin{enumerate}
\item $\displaystyle\sum_{n=s}^t C\cdot f(n) = C\cdot \sum_{n=s}^t f(n)$
\item $\displaystyle\sum_{n=s}^t f(n) + \sum_{n=s}^{t} g(n) = \sum_{n=s}^t \left[f(n) + g(n)\right]$
\item $\displaystyle\sum_{n=s}^t f(n) - \sum_{n=s}^{t} g(n) = \sum_{n=s}^t \left[f(n) - g(n)\right]$
\item $\displaystyle\sum_{i=m}^n 1 = n - m + 1$
\item $\displaystyle\sum_{i=1}^n \frac{1}{i} = H_n$, where $H_n$ is the nth harmonic number.
\end{enumerate}
\subsection{Solving}
\begin{equation}
\begin{split}
m &= \sqrt{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}\\
&= a + b(m - 1) + cn\sum_{p=2}^{m}\frac{1}{p}\\
&= a + b(m - 1) + cn\left(\sum_{p=1}^{m}\frac{1}{p} - \sum_{p=1}^{1}\frac{1}{p}\right)\\
&= a + b(m - 1) + cn(H_m - 1)\\
&= a - b + bm + cnH_m - cn\\
&= a - b + b\sqrt{n} + cnH_\sqrt{n} - cn
\end{split}
\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}))\]
We use the logarithm identity $log_b(x^d) = dlog_b(x)$ to simplify and yield:
\[T(n) \in \mathcal{O}(nlog(n))\]