What is complexity of checking whether a natural number is a perfect square? [closed]

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.

• What do you think? – Yuval Filmus Jan 17 '15 at 15:12
• Welcome! While this is indeed a question/answer site, it would help us a lot if you indicated what you tried and where you got stuck, so we could tailor our answers to your level of expertise. – Rick Decker Jan 17 '15 at 20:16
• In addition to the other helpful comments, what complexity model do you want to use? Do you want to count bit-operations? Or do you want to treat each addition/multiplication/etc. as $O(1)$ time regardless of how big the operands are? – D.W. Jan 18 '15 at 6:50
• Did you mean to ask about the time complexity of checking whether an n-digit natural number is a perfect square? – Francesco Gramano Jan 18 '15 at 18:41

For a given number $n$, binary searching for the square root $\sqrt n$ solves this problem in time $O(\log n)$.
• How? $\:$ (I can't think of any way to avoid having having binary search do $\hspace{1.81 in}$ $\Omega(\log(n))$ additions of $\Omega(\log(n))$-bit numbers.) $\;\;\;\;$ – user12859 Jan 18 '15 at 5:35
• I think multiplication and addition are taken to be $O(1)$ here. In which case this is legitimate. – Jake Jan 18 '15 at 8:58