What does "with all but negligible probability" mean?
$\Omega(n)$ is a mathematical notation from the same family that the notation $O(n)$ comes from.

To review, $O(n)$ is bounded from above; that is, if we say that $f(n) = O(g(n))$, what we're actually saying is that, for all sufficiently large $n$, there exists a constant $c &gt; 0$ such that $f(n) &lt; c \cdot g(n)$, that is, $f(n)$ grows no faster than $g(n)$.

$\Omega(n)$ is the same, except that it is bounded from below; that is, if we say that $f(n) = \Omega(g(n))$, then (for all sufficiently large $n$) there exists a constant $c &gt; 0$ such that $f(n) &gt; c \cdot g(n)$, that is, $f(n)$ grows at least as fast as $g(n)$.

Hence, what they mean when they say $1 - 2^{-\Omega(n)}$, there's a constant $c$ such that the probability of success is always $&gt; 1 - 2^{-cn}$ (except for possibly small $n$); hence, for large $n$, the probability is quite high (however, that doesn't say what "large" means in this context :-)

In case you're wondering, from the same family, we also have "little-oh" notation $f(n) = o(g(n))$ ("f grows strictly slower than g"), little-omega notation $f(n) = \omega(g(n))$ ("f grows strictly faster than g") and theta notation $f(n) = \Theta(g(n)))$ ("f grows as fast as g, within multiplicative upper and lower bounds")