What does it mean if a probability $p$ is bounded by $poly(n)$?

46 Views Asked by At

So I am supposed to give a randomized algorithm that solves a problem with probability

$$q > p \ge {1 \over poly(n)}.$$

I assume that $poly(n)$ means something like $O(n^k)$, but what kind of values does $1/poly(n)$ take then?

1

There are 1 best solutions below

0
On

You're supposed to give an algorithm such that there exists a polynomial function $f$ such that $p(n)\ge 1/f(n)$ for all $n$?