2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Jika
    Jun 20, 2014 at 14:21
  • $\begingroup$ 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. $\endgroup$
    – Paradox
    Jun 20, 2014 at 14:46

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Paradox
    Jun 20, 2014 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.