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.

Transcribed Image Text:

С 3 {x + у:хE A and y € B}