What is complexity of checking whether a natural number is a perfect square? As the title says, what is complexity of checking whether a natural number is a perfect square?
For a given number $n$, binary searching for the square root $\sqrt n$ solves this problem in time $O(\log n)$.