Time Complexity Baby Steps Giant Steps

Question

This has been driving me mad. On wikipedia's page on baby steps giant steps it gives the time complexity of the algorithm as $O(\sqrt n)$. It even gives looking up a value in a hash table as how you would implement that in practice. The thing that's confusing me is my understanding of a hash table means that would only be $O(1)$ for looking at the left coordinate. Your specifically looking at the right coordinate, which I could see being done in a $O(\log \sqrt n) = O(\log n)$ time which would give a $O(\sqrt n \log n)$ (because you'd have to reapply it $\sqrt n$ times) . But most everywhere else I'm reading indicates the time for baby-steps giant steps is $O(\sqrt n)$. What am I misunderstanding?