2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ "$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? $\endgroup$ – Raphael Aug 5 '12 at 14:54
  • 3
    $\begingroup$ In what model of computation? $\endgroup$ – JeffE Aug 6 '12 at 22:20
3
$\begingroup$

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).

$\endgroup$

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.