I am reading the book Randomized Algorithms By Motwani and Raghavan, and one of their exercises gives a modification of Karger's Min-Cut algorithm(Both is Monte Carlo) which picks two vertices and contracts them instead of an edge. You then have to show that the probability of this modified algorithm suceeding is exponentially decreasing. I have solved the exercise and my result says that the probability of the modified algorithm succeeding is less than $(\frac{7}{8})^{\frac{n}{4}}$. The original algorithm says that there is a probability larger than $\frac{2}{n^{2}}$ for success. So we have:

  • Original probability of success: At least $\frac{2}{n^{2}}$
  • Modified probability of success: Less than $(\frac{7}{8})^{\frac{n}{4}}$

So what I am trying to decipher is what exponentially decreasing probability means exactly, for the modified algorithms probability we have a base of $\frac{7}{8}$ which is a proper fraction, and a exponent that increases when $n$ increases. So each time $n$ increases it clearly gets smaller and smaller. For our original probability we have $\frac{2}{n^{2}}$, this probability of success also gets smaller and smaller when $n$ increases, but this is not considered exponentially small? is it called polynomial small then?


1 Answer 1


A quantity is exponentially small (with respect to parameter $n$) if it is $\Omega(\alpha^n)$ and $O(\beta^n)$ for some $\alpha,\beta \in (0,1)$.

A quantity is polynomially small if it is $\Omega(n^{-a})$ and $O(n^{-b})$ for some $a,b > 0$.

Let me stress that these definitions are not standard. There are otherwise to define these notions. For example, you could be more strict, and require an exponentially small quantity to be $\Theta(\alpha^n)$; or you could be more lax, and require a polynomially small quantity to be $\Omega(n^{-a})$ (without a matching upper bound). In many (but not all) cases, these are informal, qualitative concepts, which can be made precise in several different ways.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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