Shanks's Babystep Giantstep Algorithm running time BigO
This is because, the elements of the full group conceptually end up in an $n\times n$ table, and the comparison of the column (giant step list) must be done on every row of length $n$ since the overlap of the lists is in a single unique row (which allows you to determine the answer you're looking for, e.g., discrete log uniquely). So you repeat the comparison at worst $n$ times, on average $(n+1)/2$ times until you find a collision.

The presentation on Wikipedia is quite good, their $m$ being your $n$ since your listsize $n$ is $\lceil \#G \rceil$, so roughly the square root of the size of the group.