Naive Polynomial Multiplication

poly_mult.py

def naive_poly_mul(A, B, n):
    """
    Multiplies two n -1 polynomials A and B

    Args:
    A(x) = a_n-1 * x^n-1 + a_n-2 + ... + a_1*x + a_0
    B(x) = b_n-1 * x^n-1 + b_n-2 + ... + b_1*x + b_0

    Returns:
    C(x) = c_2n-2 * x^2n-2 + c_2n-3 * x^2n-3 + ... + c_1 * x + c_0
    where:
    c_2n-2 = a_n-1 * b_n-1
    c_2n-3 = a_n-1 * b_n-2 + a_n-2 * b_n-1
    ...
    c2 = a_2 * b_0 + a_1 * b_1 + a_0 * b_2
    
    e.g
    n = 3
    A(x) = a_2 * x^2 + a_1 * x + a_0
    B(x) = b_2 * x^2 + b_1 * x + b_0
    
    C(x) = c_4 * x^4 + c_3 * x^3 + c_2 * x^2 + c_1 * x^1 + c_0
    c_4 = a_2 * b_2 
    c_3 = a_1 * b_2 + a_2 * b_1
    c_2 = a_2 * b_0 + a_1 * b_1 + b_2 * a_0
    c_1 = a_1 * b_0 + b_1 * a_0
    c_0 = a_0 * b_0
    
    Running time: 
    O(n^2)
    """
    product = [0] * (2 * n - 1)
    for i in range(n):
        for j in range(n):
            product[i + j] = product[i + j] + A[i] * B[j]
    return product