Introduction

math.isqrt(n) returns the floor of the square root of a non-negative integer using integer arithmetic only. The important complexity detail is that it should be analyzed in terms of the bit length of n, not the numeric value of n itself. That is why simple claims such as O(log log n) are incomplete or misleading.

The Right Input Size Measure

If n has k bits, then the input size is k = n.bit_length(). For big integers, the cost of arithmetic on k-bit numbers is not constant.

That matters because math.isqrt does not just count iterations. Each refinement step performs large-integer operations whose cost grows with k.

So there are really two layers to the analysis:

• how many refinement steps occur
• how expensive the large-integer arithmetic is in each step

High-Level Algorithmic Picture

CPython's implementation is highly optimized C code that avoids floating-point conversion. The algorithm uses integer methods that converge quickly and are much better suited to arbitrary-precision integers than naive trial search.

At a high level, the number of refinement stages grows slowly with the bit length, roughly logarithmically in k or better depending on the view of the recursion. But that is not the whole runtime story, because each stage uses arithmetic on large integers.

Why O(log log n) Alone Is Not Enough

You may see O(log log n) quoted based on the number of Newton-style refinement steps. That ignores the cost of big-integer multiplication and division.

Under a realistic cost model, the runtime depends on the complexity of arithmetic on k-bit numbers. A more honest statement is this:

• iteration count grows very slowly
• overall runtime is dominated by big-integer arithmetic on numbers of size about k bits

So in terms of input size, the function is very fast and far better than naive search, but its total cost is not captured by a unit-cost O(log log n) headline.

A Practical Way to Think About It

For everyday use, math.isqrt is effectively the right tool. It is exact, avoids floating-point precision issues, and scales very well to large integers.

A simple benchmark shows the trend without pretending to derive a closed-form proof:

1import math
2import random
3import time
4
5for bits in [128, 512, 2048, 8192, 32768]:
6    n = random.getrandbits(bits)
7    start = time.perf_counter()
8    math.isqrt(n)
9    elapsed = time.perf_counter() - start
10    print(bits, elapsed)

The runtime grows with bit length, but much more gently than naive methods that would inspect candidates one by one.

Better Than Naive Alternatives

Compare math.isqrt conceptually with these approaches:

• trial incrementing until x * x > n, which is hopelessly slow
• binary search over candidate roots, which is much better but still less specialized
• 'int(math.sqrt(n)), which uses floating point and is not reliable for huge integers'

math.isqrt exists precisely because exact integer square roots deserve a dedicated integer algorithm.

Common Pitfalls

A common mistake is analyzing the function as if arithmetic on arbitrarily large integers were constant-time. That makes the asymptotic statement look simpler than it really is.

Another mistake is describing the complexity only in terms of the numeric value n instead of the input size k = log n. Algorithm analysis for big integers should be based on bit length.

A third issue is using math.sqrt and then casting to int for huge values. That may work for small numbers but is the wrong tool for exact large-integer roots.

Summary

• Analyze math.isqrt in terms of bit length, not raw numeric magnitude
• The function uses fast integer methods and avoids floating-point error
• A plain O(log log n) statement is incomplete because big-integer arithmetic is not free
• In practice, math.isqrt scales very well and is the correct exact tool for integer square roots
• For large integers, it is both safer and faster than floating-point or naive search approaches