this is for holding javascript data
Jeremy Ting edited p3.tex
about 10 years ago
Commit id: dc848a01e205bd5cb7382aa711bff387c6de4b74
deletions | additions
diff --git a/p3.tex b/p3.tex
index 789ee93..dd4518e 100644
--- a/p3.tex
+++ b/p3.tex
...
Squaring a number is like multiplying two $n$ bit numbers and using Gauss' observation, it takes $O(n^{1.59})$ time. Taking mod on the order of $2^o$ is simple because you do a shift that takes constant time and the answer is the bits you were shifting. So the cost of recombining is $O(n^{1.59}$. SO using Master Theorem:
\[T(n) = 1*T(\frac{n}{2}) + O(n^{1.59})\]
Using the theorem, lg(1) < 1.59m so cost of recursion is $n^{1.59}$, and we need to do recursion $n$ times. Since $y=2^n$, we need y = 1 until we can stop. So total time is:
\[O(n^{2.59})\]
\end{itemize}