Divide-and-conquer: Polynomial multiplication time complexity

Question

When I was learning the divide and conquer approach, I came to this example (https://www.geeksforgeeks.org/multiply-two-polynomials-2/) about polynomial multiplication. I cannot understand why the time required to add four results (subproblems) is Theta(n). I thought the addition only takes constant time. Why linear time? Thanks in advance!

Answer 1

You're right. But here "to add all results" means the sum of multiplies of each power of x together to find the final result which is a polynomial, i.e., the sum of multiplies of x, x^2, ..., x^n. In this sense, the sum of the four polynomials with power of O(n), takes O(n).