This is homework assignment on proving algorithm time complexity using Master Theorem. I have been trying to solve it for several hours by now with no luck. Can someone please at least explain, what is this task about and how should I solve it? Any hints would be appreciated.
Long numbers multiplication.
Any number with $2N$ digits can be written as $10^{N}A+B$, where $A$ and $B$ have $N$ digits.
For example $20481024 = 10000 \cdot2048+1024$
Product of such two numbers will be:
$(10^{N}A+B)\cdot (10^{N}C+D) = (10^{2N}\cdot AC + 10^{N}(AD+BC)+BD)$.
We can sum 2 numbers in constant time. Multiply by $10^{N}$ = write appropriate number of zeros at the end of the number.
Numbers with $N$ digits will be multiply by recursive calling the same algorithm. Recursive algorithm can be improved by following trick: Instead of four multiplications of half-length numbers, we will multiply just three:
we count $AC,BD$ and
$$(A+B)\cdot (C+D) = AC+AD+BC+BD$$, whereas when subtraction $AC$ and $BD$ from the last product, we will get exactly $AD+BC$.
Prove time complexity of such algorithm using Master Theorem.
Best Answer
Let $T(n)$ denote the time complexity of multiplying two $n$ digit numbers.
Your algorithm states that addition and subtraction is cheap (constant time). Also, you can perform a multiplication of two $2n$ digit numbers by performing 4 small multiplications on $n$ bit numbers - $AC, AD, BC, BD$. However, you can reduce this to three multiplications by noting that $AD+BC = (A+B)\cdot(C+D)-AC-BD$. So, $$(10^nA + B)\cdot(10^nC + D) = 10^{2n}AC + 10^n((A+B)\cdot(C+D)-AC-BD)) + BD $$ Note that each of $(A+B)$ and $(C+D)$ is atmost $n+1$ digits. So, multiplying two $2n$ digit numbers boils down to two $n$ digit multiplications ($AC$ and $BD$), one $n+1$ bit multiplication ($(A+B)\cdot(C+D)$), two additions, and two subtractions. Addition and subtraction are constant time. Also note that multiplying two $2n$ digit numbers takes $T(2n)$. Hence, $$T(2n) = 2T(n) + T(n+1) + \Theta(1)$$ or, $$T(n) = 3T(n/2) + \Theta(1)$$ Note that in the second equation, I have done away with ceiling and floor functions, and so $T((n+1)/2)$ has been converted to $T(n/2)$. This is a very common slight abuse when calculating asymptotic complexities. Now, you can apply the Master theorem to this recurrence relation.