While reading these lecture notes: http://www.cc.gatech.edu/%7Evigoda/7530-Spring10/Kargers-MinCut.pdf, there is an recurrance relation:
$$ {\rm P}\left(n\right) \geq 1 - \left[1 - {1 \over 2}\,{\rm P}\left(\lfloor{n \over \sqrt{\,2\,}\,}\rfloor + 1\right)\right]^{2} $$ where ${\rm P}(n)$ is some constant (probability) for small enough $n$,
which is solved to $\displaystyle{{\rm P}\left(n\right)=\Omega\left(1 \over \log\left(n\right)\right)}$
I'm not sure how this is derived, anybody give me a clue?
Variable sub to make things a bit easier:
$$\begin{align} Q(m) & = P\left(\sqrt 2 ^ m\right)\\ & \approx 1 - \left(1 - k\, Q(m - 1)\right)^2 \text{ for } k = {1\over 2}, 0 \le Q \le 1 \\ \end{align}$$
So I did a little research on this type of recursion, apparently it is called a "quadratic map". And apparently these are pretty hard, and usually unsolvable. Change of variables again to $R(m) = k - k^2\,Q(m)$, so $Q(m) = \frac{k - R(m)}{k^2}$:
$$\frac{k - R(m)}{k^2} = 1 - \left(1 - \frac{k - R(m-1)}{k^2}\right)^2$$ $$R(m) = R(m - 1)^2 + c$$
$c = \frac 14$ and $\frac 14 \le R(m) \le \frac 12$ and it is increasing towards $\frac 12$. (You might notice that this is a special case of the Mandlebrot Fractal recurrence, fun how unexpected acquaintances are always showing up in math problems).
The best I can do for finding the asymptotic behavior myself (abusing notation a lot) is $P \in \Omega\left(\frac {1} {\log n}\right) \equiv Q \in \left(\frac {1} {n^{\Omega(1)}}\right) \equiv R \in \left(-n^{-O(1)}\right)$, finding a bound on $R$ like $0.5 - \frac{z_1}{m^y} \le R(m) \le 0.5 - {z_2 \over m^{y+1}}$ for some $z_1$, $z_2$ and $y$ would satisfy the bounds. Taking $y = 1$:
$$0.5 - \frac{z_1}{m} \le R(m) \le 0.5 - \frac{z_2}{m^2}$$ $$0.5 - \frac{z_1}{m} \le R(m - 1)^2 + 0.25 \le 0.5 - \frac{z_2}{m^2}$$ $$0.5 - \frac{z_1}{m} \le \left(0.5 - \frac{z_1}{m - 1}\right)^2 + 0.25 \land \left(0.5 - \frac{z_2}{(m-1)^2}\right)^2 + 0.25 \le 0.5 - \frac{z_2}{m^2}$$ $$0 \le \frac{m(z_1^2 - z_1) +z_1}{m^3 - 2m^2 + m} \land 0 \le \frac{2m^3z_2-m^2z_2^2-5m^2z_2+4mz_2-z_2}{m^6-4m^5+6m^4-4m^3+m^2}$$
Which eventually holds for $z_1 > 1$ and $z_2 > 0$, so the bounds are correct.
It might be worth messaging (or if you are a student, or can fake being a student, visiting) the professor directly. This could be a simple case of some more well known statistical relation. I've never had a Gatech prof be less than helpful when asked directly.