# 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?

• 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