Una matriz de determinante (ingenuamente) puede ser calculado en $O(n!)$ pasos, o con una adecuada descomposición LU $O(n^3)$ pasos. Esto supone que todos los elementos de la matriz son constantes. Si, sin embargo los elementos de la matriz son polinomios (decir univariante de max orden de $p$) en cada paso de la descomposición LU de un elemento se multiplica por otro elemento de la producción (en promedio) cada vez más de polinomios. Cada paso, por lo que tarda más tiempo y más largo es el costo de realizar la descomposición todavía un polinomio?
EDIT: Para aclarar mi razonamiento un poco, si el polinomio (el uso de la FFT como J. M. sugiere en los comentarios) tarda $O(m \log m)$, y debemos realizar $O(n^3)$ operaciones para obtener la descomposición LU, cada paso el polinomio efectivamente podría duplicar en el grado en cada multiplicación*. El tiempo de ejecución sería algo como
$$ \approx O \left ( \sum_{k}^{n^3} (p \ln p)^{2k} \right ) .$$
* (no muy a hacerlo, y aquí es donde estoy atascado)
