# What's the complexity of expanding a general polynomial?

Suppose I have a polynomial in the form $(a_1 x_1+ a_2 x_2+...+ a_m x_m)^n$, where $x_1,...,x_m$ are the independent variables. I want to expand it to the form of sum of products. What is the complexity,i.e. the big O notation?

• If, as input, you have $a_1x_1+\cdots+a_mx_m$ and you have $n$ then you can use modular exponentiation to calculate it. On the other hand, if, as input, you have $m$ and $n$ then the complexity will be the modular exponentiation + the complexity of calculating the polynomial.
– Jika
Jun 20, 2014 at 14:21
• Thanks for your reply. I have $a_1x_1+...+a_mx_m$ and $n$ as input. Can you introduce more how to calculate it use modular exponentiation? I am new to this field. Jun 20, 2014 at 14:46

If you consider your polynomial $X=a_1x_1+\cdots+a_mx_m$, then you want to calculate the complexity of the operation $X^n$. As far as I know, it depends on the method used and the best algorithm to do $X^n$ is exponentiation by squaring which is given, for example, heretime complexity of exponentiation by squaring.
As you can see, in the worst case, you will divide $b$ ($n$ in your case) by 2 until you reach $1$ and then you immediately reach $n=0$. The complexity of this step is $\log_2n$ (if $n$ was written in binary $n=2^p$, you have to divide $p$ ($=\log_2n$) times to reach $1$).
If you want to calculate the complexity of expanding the polynomial without having it (you do not have $X$). So you have as input a vector x=[x_1, ..., x_m] and a vector a=[a_1, ..., a_m], you need to do a multiplication a_i*x_i and a summation and use a formula to get $\left(\sum a_ix_i\right)^n$ which will be a different complexity than I wrote above.
• Thanks. My question is , for example I have $(2x_1+3x_2+2x_3)^4$, I want to expand it in form of sum of products. I want to measure the complexity of general operation like that. I will try the method you suggested. Thanks. Jun 20, 2014 at 15:40