Given two polynomials $P_A(n)=a_{n-1}{x}^{n-1}+a_{n-2}{x}^{n-2}+dots{a}_0$ and $P_B(n)=b_{n-1}{x}^{n-1}+b_{n-2}{x}^{n-2}+dots{b}_0$

design a subquadratic $(o(n^2))$ time algorithm to multiply the two polynomials. You can assume that the

coefficients $a_i$ and $b_i$ are $O(logn)$ bits and can be multiplied in $O(1)$ steps.

Note: Don't use Fast Fourier Transform based methods since it has not been discussed in class.