Currently I am working on a problem that is hard for me to understand as I am new to algorithms.
The problem says :
Represent the polynomial $p(n) = a_0 + a_1n + a_2n^2 + · · · + a_dn^d $ of degree d by an array
P[0 . . d] containing its coefficients. Suppose you already have an algorithm capable of multiplying a polynomial of degree k by a polynomial of degree 1 in a time in O(k), as well as another algorithm capable of multiplying two polynomials of degree k in a time in O(k log k). Let $n_1, n_2, . . . , n_d$ be integers.
Give an efficient algorithm based on divide-and-conquer to find the unique polynomial p(n) of degree d whose coefficient of highest degree is 1, such that $p(n_1) = p(n_2) = . . . = p(n_d) = 0$. Analyse the efficiency of your algorithm.
I don't understand where to begin and also what's the purpose of giving an algorithm that multiplies two polynomials of degree k in O(k log k) ?
Answer polynomial is $(x-n_1)(x-n_2)...(x-n_d)$
Algo is this:
Let $P(a,b) = (x-n_a)...(x-n_{b-1})$, we need found $P(1, d+1)$ $P(a,a+1)$ is O(1) operation if $2 | b-a$, let $c = \frac{a+b}{2}$ and $P(a,b) = P(a,c)P(c,b)$ in another case, $P(a,b) = P(a, b-1)P(b-1, b)$