0
$\begingroup$

I am considering the asymptotic analysis required to convert a polynomial of the shape

$$P(x) = \prod_{i = 1}^{n}(1 + x^{s_i})$$

to its "full" representation, for example $$P(x) = 1+x^3+x^5+x^8+x^9+x^{12}+x^{14}+x^{17}.$$

Now, it would appear to me that we perform $n$ repetitions of performing $2^i$ multiplications, as for every expansion, we double the number of terms, as an example: $(1+x^2)(1+x^4)=1+x^2+x^4+x^6$. However, this smells a bit to me.

What is the asymptotic running time of expanding $P(x)$?

Note: Evaluating the polynomial may be done in $O(n\; t \log t$) using FFT, this is one solution.

$\endgroup$
8
  • $\begingroup$ You are thinking of a specific algorithm to multiply those polynomials. Is your question to compute the number of operations in that particular algorithm? There are faster algorithms to solve the problem, using Fast Fourier transform. $\endgroup$
    – plop
    Apr 29 at 14:50
  • $\begingroup$ In general, I would just like to know what the running time is, if we just rely on (regular) multiplication. The idea of this algorithm is to solve the subset sum problem, by evaluating P(x) as defined above. However, I want to know what the running time is with no "tricks". I am indeed aware of FFT, but I would not consider it in this instance, unless it makes sense to use it at every repetition? I'm not certain. $\endgroup$ Apr 29 at 15:11
  • $\begingroup$ Ok. From what you say ('with no "tricks"') I think you do mean the running that of the particular algorithm that consists of for each factor apply associativity to "open its parenthesis" and cancel terms of the same degree. My first comment was to make you notice that one can speak of running time for a particular algorithm, not for a problem. For a problem, we could consider the running time of the fastest algorithm that solves it (if such a notion exists) or something like that. A single problem can be solved by many algorithms with running times that might be hard to compare. $\endgroup$
    – plop
    Apr 29 at 15:19
  • $\begingroup$ I think you hit my confusion right on the nail. I suppose one running time would be O(n t log(t) ) if we simply use FFT? $\endgroup$ Apr 29 at 15:22
  • 1
    $\begingroup$ It's not clear to me what you want the input to be and what you want the output to be. Is the output a representation of the polynomial, e.g., its coefficients? Is the output a number, namely, the result of evaluating the polynomial at a particular input? Note that the running time to output a polynomial with $n$ terms has to be at least $n$, since it takes that long just to write the output. Now can you answer your own question, and prove that your answer is optimal? $\endgroup$
    – D.W.
    Apr 30 at 7:31

Your Answer

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

Browse other questions tagged or ask your own question.