# Question about what exponentially small probability of success means in randomized algorithms

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?

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.