this is for holding javascript data
Xavier Holt edited begin_claim_The_algorithm_runs__.tex
about 8 years ago
Commit id: c29e2bb06914e2caf93ac9f5f027a6d68e3b22d9
deletions | additions
diff --git a/begin_claim_The_algorithm_runs__.tex b/begin_claim_The_algorithm_runs__.tex
index f6bcbaa..796a71c 100644
--- a/begin_claim_The_algorithm_runs__.tex
+++ b/begin_claim_The_algorithm_runs__.tex
...
R(n) &= 2R(n/2) + O(\log n) + O(n) \\
&=2\left(2R(n/4) + O(\log n/2) + O(n/2)\right) + O(\log n) + O(n)\\
&= iO(n) + \sum_{j=0}^{i-1} 2^j O(\log \frac{n}{2^i}) + 2^iR(\frac{n}{2^i})\\
&= O(n\log n) + \sum_{j=0}^{\log n-1} 2^j O(\log \frac{n}{2^i}) + 2^{\log n}R(1)
\tag{as}\\ \tag*{as}\\
&= 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)\\
&= O(n\log n) + O(n) + \left(\log n 2^{\log n} - C \right) \tag{with $C\geq0$}\\