# Run time of product of polynomially bounded numbers

Let $M$ denote a set of $n$ positive integers, each less than $n^c$.

What is the runtime of computing $\prod_{m \in M} m$ with a deterministic Turing machine?

• "$m \in O(n^c)$" does not hold meaningful information. As $M$ is a finite set of constant values, we can use $c=0$ and $d=\max M$ as Landau-constant, or $c=1$ and any $d$ to fulfill the requirement. Do you mean to say that $c,d$ are known and fixed for a whole class of such sets $M$? And again: what have you tried? – Raphael Aug 5 '12 at 14:54
• In what model of computation? – JeffE Aug 6 '12 at 22:20

## 1 Answer

Computing the product sequentially, we need to perform $n-1$ multiplications of numbers of size $O(C^n n^{cn})$, for some constant $C$ corresponding to the constant in $O(n^c)$. Using algorithms for fast integer multiplication, each of these requires $\tilde{O}(C\log n + cn \log n) = \tilde{O}_c(n)$, so in total the time is $\tilde{O}_c(n^2)$ (the $\tilde{O}$ hides logarithmic factors).