2
$\begingroup$

What is meant by saying an algorithm runs in time $Poly(|S|,n,\frac{1}{\epsilon})$.

Can somebody explain with an example.

$\endgroup$
3
  • 1
    $\begingroup$ This is hard to answer without any context. Notation often depends upon the context in which it is used. Will not migrate to Computer Science until the question is improved. $\endgroup$ Mar 5, 2013 at 9:58
  • $\begingroup$ @DaveClarke: I don't think this is ambiguous; Schaull's answer is exactly right. $\endgroup$ Mar 5, 2013 at 18:51
  • $\begingroup$ @HuckBennett: Perhaps it is simply a matter of unfamiliarity on my part (and the OP's). $\endgroup$ Mar 5, 2013 at 19:02

1 Answer 1

5
$\begingroup$

It means that there exists a polynomial $f(x,y,z)$ such that the algorithm runs in time $f(|S|,n,\frac{1}{\epsilon})$.

Specifically, it means that there are constants $c_1,c_2,c_3\ge 0$ such that the algorithm runs in time $O(|S|^{c_1}\cdot n^{c_2}\cdot (\frac{1}{\epsilon})^{c_3})$.

$\endgroup$
4
  • $\begingroup$ In the big O, why is it multiplying the parameters rather than adding them? $\endgroup$
    – c-o-d
    Dec 13, 2014 at 18:50
  • $\begingroup$ Because that's how polynomials work - you're allowed to multiply factors by one another. To make this a little more concrete, think of a polynomial $f(x,y,z)$, then $x\cdot f(x,y,z)$ is also a polynomial, and then you have to multiply the monomials by one another. $\endgroup$
    – Shaull
    Dec 13, 2014 at 19:01
  • $\begingroup$ Thanks, so then conceivably you could also have something like: $O((|S| + someconstant)^{c_1} \cdot (n - 2)^{c_2} * (\frac{1}{\epsilon})^{c_3})$ as well? $\endgroup$
    – c-o-d
    Dec 13, 2014 at 19:10
  • $\begingroup$ Yes, certainly. $\endgroup$
    – Shaull
    Dec 13, 2014 at 21:02

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