Algoritmo efficiente per tradurre/cambiare polinomi

Question

Ho un polinomiale $ p (x) $ e, dato alcuni $ d $ costante, devo trovare il polinomiale $ p (x+d) $. Ad esempio, se $ p (x) = x^2 $ e $ d = 1 $, il risultato sarebbe $ p (x+1) = (x+1)^2 = x^2+2x+1 $ (con i coefficienti immagazzinati in un array/vettore).

Conosco l'algoritmo con $ o (n^2) $ complessità tempo, che si basa sul metodo di Horner: $$ a_0+(x+d) (a_1+(x+d) (a_2+...+(x+d) a_n )) $$ Tuttavia, non è abbastanza efficiente per le mie esigenze. Esiste un algoritmo più efficiente per risolvere questo problema?

PS I coefficienti e $ d $ saranno sempre numeri interi, se questo aiuta.