I have read Horner's rule for polynomial evaluation which does the work for O(n) where n is the degree of polynomial. Example: Let's take a polynomial of degree 3 -> 3x^3+ x^2 + 9 We are given many value of 'x' and a coefficient vector like [3,1,0,9] and let's take 'x' take to be 3 then it will be evaluated as 3*3^3 + 3^2 + 9 = 81+9+9 = 99 so the answer will be 99. Let's say we have q queries so Horner's rule will take O(nq). Is there any better algorithm? I have heard about FFT and DFT and I have consulted many resources but all in vain. Can anyone help me to understand it please?