What's the complexity of expanding a general polynomial?

Question

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?

Answer 1

If I understand your question good.

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.

I hope it helps.