Question

Design a brute-force algorithm for multiplying two polynomials, both are expressed as functions of x, and show that its time efficiency of O(n^2).

Answer 1

suppose polynomials are presented as array
Poly1[] = {a₀,a₁,..... a_n-2, a_n-1}
Ploy2[] = {b₀,b₁,..... b_n-2, b_n-1}

The first input array represents a₀ + a₁x¹ + a₂x² +....+ a_n-1x^n-1
The second array represents b₀ + b^₁x^1 + b₂x² +....+ b_n-1x^n-1

Algorithm to multiply both polynomial poly1 and poly2
solution is to consider every term of first polynomial and multiply it with every term of second polynomial.
multiply(Poly1[0..n-1], Poly2[0..n-1])
step 1) Create a result array output[] of size 2*n-1.
step 2) Initialize all entries in output[] as 0.
step 3) Traverse array Poly1[] and do following for every element poly1[i]
Traverse array Poly2[] and do following for every element Poly2[j]
output[i+j] = output[i+j] + Poly1[i] * Poly2[j]
step 4) Return output[].

Time complexity = O(n^2)