41 How fast can we multiply two n-digit numbers ?

Following operations can be done in constant time:

• Multiplying two bits
• Adding two bits

Need to add $O(n)$ binary strings, and each binary string takes $O(n)$ time to compute. Hence the total running time is $O(n^2)$

Lets find about squaring

$T(n)=$ time needed to square an $n$-bit number. $T(n)$ can be upper bounded by $O(n^2)$

1. Compute $z^2$
2. Compute $y^2$
3. Obtain $2\cdot z\cdot y$ by computing $(y+z{)}^2$ and subtracting $z^2$ and $y^2$