I'm reading the wiki page of Karger's algorithm for a self-study of CLRS to get some and I'm confused by one of the bounds they have.

Here, under the section about finding all min cuts, they have this line $$(1-P(n))^{O(\log^{2} n)} \le (1-\frac{c}{\ln n})^{\frac{3}{c} \ln^{2} n}$$. I get that they are using the definition of big O to insert these constants, but what feels fishy to me is the choice for the constant in the exponent of $\log^{2} n$ of $\frac{3}{c}$. Why can't I just choose the coefficient to just be, $\frac{2}{c}$ and get a tighter bound? How do they know here that $\frac{3}{c}$ is the smallest coefficient that may be chosen?

I understand the rest of the argument, for the record (They're using $e^{x} \ge 1+x$)

  • $\begingroup$ Hint: do away with the abuse of notation first, i.e. replace $O(\_)$ with a function $g \in O(\_)$ (symbolically). (I wonder if they actually need $\Omega$, but that may depend on $P$.) $\endgroup$ – Raphael Apr 15 '15 at 9:17

$$(1-P(n))^{O(\log^{2} n)} \le (1-\frac{c}{\ln n})^{\frac{3}{c} \ln^{2} n}$$

First, to get a tighter bound, you should choose $\frac{4}{c}$ or larger, instead of $\frac{2}{c}$ or smaller.

In particular, the probability for $\frac{2}{c}$ is $$\textrm{Pr}[\textrm{miss any min-cut}] \le O(1).$$ This does not make sense for a probability value.

Second, the larger the chosen coefficient is, the higher the time complexity of the algorithm is (to achieve a tighter bound). That is, there is a trade-off.


The point here is that at the end the argument will use a union bound over all the $O(n^2)$ min cuts. So the failure probability for a single minimum cut needs to be $o(n^{-2})$ for this to give any useful information.

An alternative would be to try and replace the union bound with a more precise argument, but since a cycle has $\Omega(n^2)$ min cuts, this won't work in general.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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