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)$

  • $\begingroup$ Thank you, could you please provide a little bit of explanation please ? Appreciated $\endgroup$ – Zok Feb 24 '17 at 1:50
  • $\begingroup$ It is a calculation order with useing only the operations we are already have. If power is even - we use divide-and-concqueror and unite results by fast multiplication. If power is odd - we reduce power to 1 $\endgroup$ – kotomord Feb 24 '17 at 1:53
  • $\begingroup$ So this is a final answer or a first step to resolve the problem ? And do you have a simplified one ? Because I can't even understand the algorithm.. $\endgroup$ – Zok Feb 24 '17 at 6:59
  • $\begingroup$ You need only: 1. Write a pseudocode 2. Get a complexity of this algorithm $\endgroup$ – kotomord Feb 24 '17 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.