0
$\begingroup$

As the title says, what is complexity of checking whether a natural number is a perfect square?

$\endgroup$
  • 4
    $\begingroup$ What do you think? $\endgroup$ – Yuval Filmus Jan 17 '15 at 15:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Rick Decker Jan 17 '15 at 20:16
  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Jan 18 '15 at 6:50
  • $\begingroup$ Did you mean to ask about the time complexity of checking whether an n-digit natural number is a perfect square? $\endgroup$ – Francesco Gramano Jan 18 '15 at 18:41
2
$\begingroup$

For a given number $n$, binary searching for the square root $\sqrt n$ solves this problem in time $O(\log n)$.

$\endgroup$
  • 1
    $\begingroup$ 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.) $\;\;\;\;$ $\endgroup$ – user12859 Jan 18 '15 at 5:35
  • $\begingroup$ I think multiplication and addition are taken to be $O(1)$ here. In which case this is legitimate. $\endgroup$ – Jake Jan 18 '15 at 8:58
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 1. This only works for 32-bit numbers floating point numbers. 2. This does not give the exact square root; it only gives an approximation. Both limitations should be disclosed in your answer. Also, when you are working on fixed-size inputs, asymptotic notation is inappropriate. $\endgroup$ – D.W. Jan 18 '15 at 6:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.