Consider two sets A and B, each having n integers in the range from 0 to 10n. We wish to compute the Cartesian sum of A and B, defined by

That the integers in C are in the range from 0 to 20n. We want to find the elements of C and the number of times each element of C is realized as a sum of elements in A and B. Show how to solve the problem in O(n lg n) time. Represent A and B as polynomials of degree at most 10n.

3 {x + :E A and y B}