this is for holding javascript data
Xavier Holt edited begin_claim_The_algorithm_runs__.tex
about 8 years ago
Commit id: 769fa0670eb7f5a10c31b8bc39ce045220bbc4f4
deletions | additions
diff --git a/begin_claim_The_algorithm_runs__.tex b/begin_claim_The_algorithm_runs__.tex
index ec48f63..5ea4a14 100644
--- a/begin_claim_The_algorithm_runs__.tex
+++ b/begin_claim_The_algorithm_runs__.tex
...
We obtain the following after `unravelling' our recursive formula $i$ times:
\begin{align*}
R\left(n\right)
&= &:= O\left(n\right) + 2R\left(\frac{n}{2}\right)+ O\left(\log n\right)\\
&= iO\left(n\right) + 2^iR\left(\frac{n}{2^i}\right) + \sum_{j=0}^{i-1} 2^j O\left(\log \frac{n}{2^i}\right)
\end{align*}