We want to compute $\lfloor\sqrt{x}\rfloor$ for a non-negative integer $x$, without using any built-in function.

Naive Solution

class Solution {
    public int mySqrt(int x) {
        long ans = 1;
        while (ans * ans <= x) {
            ans++;
        }
        return (int) ans - 1;
    }
}

This solution is very straightforward and runs in $O(\sqrt{x})$, but we can do much better.

Binary Search

This is fundamentally a searching problem: we want the largest integer $m$ such that $m^2 \le x$. The search space is sorted, so we just need a lower and upper bound. But observe that for any $x > 1$:

You can easily show this is true by squaring both sides:

So we binary search over $[1,\, x/2 + 1]$. The runtime is $O(\log x)$.

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;
        int l = 1;
        int r = x / 2 + 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            long square = (long) mid * mid; // cast to avoid overflow
            if (square == x) {
                return mid;
            } else if (square < x){
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        // after the loop
        // r is the largest value whose square is <= x
        // l is the smallest value whose square is > x
        return r;
    }
}

You might be surprised, but we can even do better.

Newton’s method

To compute $\sqrt{x}$, we want to solve the equation

This is equivalent to finding a root of the function

Since $\sqrt{x}$ is the value of $y$ such that $f(y) = 0$, we can use Newton’s Method to approximate it.

Where Does Newton’s Update Formula Come From?

Newton’s method is based on the idea of approximating a function by its tangent line.

Suppose we want to find a root of a function

Assume our current guess is $y_n$. Instead of working with the actual (possibly curved) function, we approximate it by its tangent line at $y_n$.

The equation of the tangent line is

Since the tangent line approximates the function near $y_n$, we estimate the root by finding where this line crosses the x-axis.

Set

Substituting,

Now solve for $y_{n+1}$:

This is Newton’s update formula:

For the square root problem,

Substituting these into Newton’s formula gives

Simplifying,

Therefore, the iteration becomes

Intuition

Suppose our current guess is $y_n$.

• If $y_n$ is too large, then $\frac{x}{y_n}$ is too small.
• If $y_n$ is too small, then $\frac{x}{y_n}$ is too large.

The next guess is simply the average of these two values:

This average moves the estimate much closer to the true square root.

Example

Find $\sqrt{10}$.

Start with the initial guess

Then

Next,

Next,

and

The true value is

After only a few iterations, the approximation is already extremely accurate.

The code is even much simpler than the binary search solution:

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;
        long r = x;
        while (r * r > x) {
            r = (r + x / r) / 2;
        }
        return (int) r;
    }
}

Runtime

If you want a Big-O in terms of the input value $x$, Newton’s method for square root is:

iterations.

However, there is a subtle distinction:

Newton iteration

The update:

has quadratic convergence: the error after one step is roughly the square of the previous error. That is why the number of correct bits doubles — it is not magic.

Let $a=\sqrt{x}$ and write the error as $e_n = y_n - a$. Substituting $y_n = a + e_n$ into the iteration and simplifying gives:

For small $e_n$, we have $a+e_n \approx a$, so:

for some constant $C$. That is quadratic convergence.

Bits of accuracy are just a logarithmic measure of error: $b$ correct bits means roughly

Plug that in:

Ignoring the constant $C$ (it only shifts things by a few bits), $2^{-2b}$ means we now have about $2b$ correct bits. So the bits roughly double each step.

Concretely, if you start with $b_0 = 5$ correct bits, Newton gives about $10$, then $20$, then $40$, then $80$. After $k$ iterations:

To get $\lfloor\sqrt{x}\rfloor$ we need about $B = \log x$ bits, so $2^k b_0 \approx B$, which means:

The chain is: quadratic convergence $\Rightarrow$ error is squared $\Rightarrow$ accurate bits double $\Rightarrow$ $O(\log\log x)$ iterations.

Why do some people say $O(1)$?

Because for a fixed integer type (like Java int):

The maximum input size is bounded. Newton takes at most around 20 iterations, so in practice:

for Java int.

But in algorithm analysis, where $x$ can grow arbitrarily large, the more meaningful answer is:

For comparison:

• Naive Solution: \(O(\sqrt{x})\)

• Binary search: \(O(\log x)\)

• Newton’s method: \(O(\log\log x)\) (and $O(1)$ for fixed-width int)

So Newton is asymptotically faster, but binary search is usually chosen in interviews because proving and implementing it is simpler.