this is for holding javascript data
Xavier Holt edited begin_claim_The_algorithm_runs__.tex
about 8 years ago
Commit id: 7b33924d3eb14266bf846319e1a4dd2884a4a086
deletions | additions
diff --git a/begin_claim_The_algorithm_runs__.tex b/begin_claim_The_algorithm_runs__.tex
index d74f063..4678240 100644
--- a/begin_claim_The_algorithm_runs__.tex
+++ b/begin_claim_The_algorithm_runs__.tex
...
&= iO\left(n\right) + \sum_{j=0}^{i-1} 2^j 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\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\left(n\right) &= iO\left(n\right) + \sum_{j=0}^{i-1} 2^j O\left(\log \frac{n}{2^i}\right) + 2^iR\left(\frac{n}{2^i}\right)\\