Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
You are given an algorithm for multiplication of two numbers, in a scenario where multiplication is slow, but addition and subtraction is cheap. You need to find the recurrence relation describing this multiplication algorithm, and using Master's theorem, find its complexity. What have you tried so far? –  Paresh Mar 3 '13 at 16:02
    
I have basic knowledge, how to solve Recurrence relation with masters theorem, but I am stuck on how to compose such relation for this task –  user64793 Mar 3 '13 at 16:06

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.