this is for holding javascript data
Xavier Holt edited begin_claim_The_algorithm_runs__.tex
about 8 years ago
Commit id: 1a849a398d08d9b7d6283213a12d3954ad0f8564
deletions | additions
diff --git a/begin_claim_The_algorithm_runs__.tex b/begin_claim_The_algorithm_runs__.tex
index 1dfc0fa..a0524fb 100644
--- a/begin_claim_The_algorithm_runs__.tex
+++ b/begin_claim_The_algorithm_runs__.tex
...
\begin{align*}
R(n) &= iO(n) + \sum_{j=0}^{i-1} 2^j O(\log \frac{n}{2^i}) + 2^iR(\frac{n}{2^i})\\
\text{When our point set contains one point, it's clear that $R(1)$ only requires a constant amount of work.}\\
\text{This occurs when $\frac{n}{2^i}=1\Rightarrow i=\log_2 n$}\\
&= O(n\log n) + \sum_{j=0}^{\log n-1} 2^j O(\log \frac{n}{2^i}) + 2^{\log n}R(1)\\
&= O(n\log n) + n^{\log 2}O(1) + \sum_{j=0}^{\log n-1} 2^j (\log n - \log{2^j})\\
&= O(n\log n) + O(n) + \left(\log n\sum_{j=0}^{\log n-1} 2^j - \sum_{j=0}^{\log n-1} 2^j\log{2^j} \right)\\