As the title says, what is complexity of checking whether a natural number is a perfect square?
closed as unclear what you're asking by Luke Mathieson, D.W.♦, David Richerby, hengxin, Ran G. Jan 18 '15 at 16:25
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
For a given number $n$, binary searching for the square root $\sqrt n$ solves this problem in time $O(\log n)$.
There is a faster way to find (a good approximation of) the square root than the current answer (for 32-bit floating point numbers): a generalization of fast inverse square root (whose generalization you can read more about from this blog post) will give you the square root of a representable number. Normally, if you take the square root of a natural number you could lose some precision in floating point arithmetic of the result, but a perfect square will have its square root perfectly representable because the square root will also be an integer.