Question

Consider two sets a and b, each having n integers in the range from 0 to 10n. Wewish to compute the cartesian sum of a and b, dened byc = fx + y j x 2 a ^ y 2 bg

Answer 1

Lets first understand the problem. A and B each have n elements which can range from 0 to 10n. C is the cartersian sum of the two sets so by the defintion fo the set given earlier, it has as many as n^2 elments

for a in set X :

for b in set Y :

insert into set C (a+b)

So, this brute force approach gives us a O(n^2) time algorithm. We are asked to find a more efficient algorithm for this – one that can solve the problem in O(n lgn ) time instead.

Solution to the problem lies in spotting the analogy of the problem with that of fast-fourier transform. FFT provides us a way to multiply two polynomials of degree-bound n in O(n lg n ) time rather than the brute force O(n^2) method for multiplying the two polynomials.

So, lets construct a polynomial A of degree 10n as follows

A(x) = \Sum_{i=0}^{10n-1} a_i x^i

where a_i = freq(i) in set A.

Similarly construct set B.

We can multiply the two polynomials in O(n ln n) time.The non-zero coefficient of the terms are the frequency of the elements in C, and the power of the non-zero-coefficient terms are the elements of C.