In Shoups well-known paper Lower bounds for Discrete Logarithms and Related Problems he proves that the Discrete Logarithm Problem is hard in the generic group model (if group operation and inverse are the only computations that can be performed on group elements). Theorem 1 in the paper says that the probability that a generic algorithm $A$ solves this problem is bounded by $\mathcal{O}(m^2/p)$ (m is the number of oracle queries, p the prime group order). The part that I don't understand is the following:
If we insist that $A$ succeed with probability bounded by a positive constant (e.g., 1/2) to the below, this theorem translates into a lower bound $\Omega(\sqrt{p})$ of the number of group operations queried by $A$.
Can someone explain this conclusion to me?