this is for holding javascript data
Jeremy Ting edited p3.tex
about 10 years ago
Commit id: 711918bac3b6dac908f215b58dcac917c7757ff4
deletions | additions
diff --git a/p3.tex b/p3.tex
index 3b7eae3..789ee93 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} 1*T(\frac{n}{2}) + O(n^{1.59})\]
\end{itemize}