As a personal exercise, I'm trying to write an algorithm to compute the n-th derivative of an ordered, simplified polynomial (i.e., all like terms have been combined). The polynomial is passed as an ordered list where the i-th index corresponds (though is not equivalent) to the coefficient of
x to the n-th power.
Take the derivative of: \$3x^3 + 5x^2 + 2x + 2\$ ->
- 1st derivative: \$9x^2 + 10x + 2\$
- 2nd derivative: \$18x + 10\$
- 3rd derivative: \$18\$
- 4th...n-th derivative: \$0\$
Implementation in Python:
def poly_dev(poly, dev): """ :param poly: a polynomial :param dev: derivative desired, e.g., 2nd """ c = 0 # correction r = dev # to remove while dev > 0: for i in range(1, len(poly)-c): poly[i-1] = (len(poly)-(i+c))*poly[i-1] dev -= 1 # I suspect this c += 1 # this can be simplified return poly[:-r]
print(poly_dev(poly = [3,5,2,2], dev = 2))
I have a math background, but I'm only starting to learn about computer science concepts like Complexity Theory.
I've intentionally tried to avoid reversing a list, as I know that can be expensive. What other steps can I change to decrease this procedure's run time?