Shanks's Babystep Giantstep Algorithm running time BigO I am working through Introduction to Mathematical Cryptography and am not in school anymore, so I don't have any advisers or peers to ask (my background is a BS in math). In the text they present the Shanks's BS-GS Algotrithm with a proof. I am having trouble figuring out how the total running time of the algorithm follows from the running time its parts. 

The algorithm says to create two lists which each have length $n$. I understand how this ends up being about $2 \cdot n$ multiplications. Then they say comparing the lists takes $\operatorname{BigO}[\log(n)]$ steps and then jump straight to "hence the total running time is $\operatorname{BigO}[n \cdot \log(n)]$." Since the steps are done separately, why do we multiply instead of add the running times?
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.