this is for holding javascript data
Xavier Holt edited begin_claim_The_algorithm_runs__.tex
about 8 years ago
Commit id: 68cf95a8e48eee1dfe2fdb6e17389fdb39681561
deletions | additions
diff --git a/begin_claim_The_algorithm_runs__.tex b/begin_claim_The_algorithm_runs__.tex
index 66aa717..d74f063 100644
--- a/begin_claim_The_algorithm_runs__.tex
+++ b/begin_claim_The_algorithm_runs__.tex
...
\begin{claim}
The algorithm runs in
$O(n\log n)$ $O\left(n\log n\right)$
\end{claim}
\begin{proof}
We obtain the following after `unravelling' our recursive formula $i$ times:
\begin{align*}
R(n) R\left(n\right) &=
O(n) O\left(n\right) +
O(\log n) O\left(\log n\right) + 2R\left(\frac{n}{2}\right)\\
&=
iO(n) iO\left(n\right) + \sum_{j=0}^{i-1} 2^j
O(\log \frac{n}{2^i}) O\left(\log \frac{n}{2^i}\right) + 2^iR\left(\frac{n}{2^i}\right)
\end{align*}
When our point set contains one point, it's clear that
$R(1)$ $R\left(1\right)$ requires a constant amount of work. This occurs when $\frac{n}{2^i}=1$ or equivalently when $i=\log_2 n$.
\begin{align*}
R(n) R\left(n\right) &=
iO(n) iO\left(n\right) + \sum_{j=0}^{i-1} 2^j
O(\log \frac{n}{2^i}) O\left(\log \frac{n}{2^i}\right) + 2^iR\left(\frac{n}{2^i}\right)\\
&=
O(n\log n) O\left(n\log n\right) + \sum_{j=0}^{\log n-1} 2^j
O(\log \frac{n}{2^i}) O\left(\log \frac{n}{2^i}\right) + 2^{\log
n}R(1)\\ n}R\left(1\right)\\
&=
O(n\log n) O\left(n\log n\right) + n^{\log
2}O(1) 2}O\left(1\right) + \sum_{j=0}^{\log n-1} 2^j
(\log \left(\log n -
\log{2^j})\\ \log{2^j}\right)\\
&=
O(n\log n) O\left(n\log n\right) +
O(n) O\left(n\right) + \left(\log n\sum_{j=0}^{\log n-1} 2^j - \sum_{j=0}^{\log n-1} 2^j\log{2^j} \right)\\
&=
O(n\log n) O\left(n\log n\right) + \left(\log n \times 2^{\log n} - C \right) \tag{with $C\geq0$}\\
&=
O(n\log n) O\left(n\log n\right) + \left(n\log n - C \right)\\
&\leq
O(n\log n) O\left(n\log n\right) +
O(n\log n)\\ O\left(n\log n\right)\\
&\in
O(n\log n) O\left(n\log n\right)
\end{align*}