Square root (O(√n))

At a glance: The operation or memory count grows with the square root of a numeric magnitude n.

Jump to: Time complexity · Space complexity · Try it yourself

Understand the growth

If a positive integer has a divisor other than one and itself, at least one factor is no greater than its square root. Testing candidate factors only up to that point is enough to determine whether an integer is prime by trial division.

Multiplying the numeric value by four doubles its square root: √(4n) = 2√n. This is slower growth than n, but faster than log n. Beware that n here refers to the value of the integer, not the number of bits needed to represent it.

Why the square-root boundary matters

A composite positive integer can be written as a × b. If both factors were greater than √n, their product would exceed n, which is impossible. Therefore at least one factor is no greater than the square root. Trial division only needs to test potential small divisors up to that boundary, making the number of candidate tests O(√n) in the simple arithmetic-operation model.

Here n denotes the integer’s numeric value. That is different from input length measured in bits. A b-bit positive integer can have magnitude close to 2^b, so a √n iteration bound may become exponential in b. For machine-sized integers this distinction is often hidden by fixed-width types, but it matters when comparing algorithms theoretically.

O(√n) also appears in square-root decomposition of arrays: partition n elements into blocks of size roughly √n, then answer certain range queries by scanning partial blocks and aggregating full blocks. Its precise cost and memory usage depend on the chosen updates, queries and block summaries.

Worked example

At numeric value 100, the square root is 10; at 10,000 it is 100; at 1,000,000 it is 1,000. When the value grows by a factor of one hundred, the maximum candidate count grows by roughly a factor of ten.

Trace trial division without a huge loop

For n = 97, the potential divisor range is 2 through 9. Because no candidate divides 97, the procedure performs eight remainder tests and returns prime. For n = 100, it finds divisor 2 immediately, so the same code is fast even though √100 = 10. The worst case is driven by inputs with no small divisor, not every composite number.

At n = 10,000, the square-root boundary is 100; at n = 1,000,000, it is 1,000. A hundredfold increase in numeric magnitude increases the candidate range about tenfold. The code uses d <= n / d rather than d*d <= n to avoid overflow when d*d might exceed the signed integer range.

Time complexity

Representative time example: Checking divisors up to √n.

The divisor loop checks successive candidates until d × d would exceed n, or a divisor is found. Writing the stopping condition as d <= n / d avoids overflow from computing d*d for large signed integers. Composite numbers with small factors exit early. A prime number near the chosen numeric magnitude usually drives the worst-case iteration count. This is an algorithmic model that treats integer arithmetic as constant cost; a bit-complexity analysis for huge integers has different assumptions.

Count divisor tests, including early exit

Each successful loop iteration performs a bounded amount of arithmetic: one quotient in the condition, one remainder in the body, and an increment. For fixed-width integers these count as constant-cost model operations. The maximum number of candidate values is approximately floor(√n) - 1 because the loop starts at 2. The exact count varies with whether n has a small factor.

A small optimization tests 2 separately and then checks only odd candidates; this improves a constant factor but retains O(√n). An advanced primality algorithm need not use trial division at all. Do not claim that O(√n) describes every prime test, or that it is polynomial in the number of input bits. The stated bound applies specifically to this implementation and the numeric-magnitude model.

C#

C# | SquareRoot.cs

bool IsPrime(int n)
{
    if (n < 2) return false;
    for (int d = 2; d <= n / d; d++)
        if (n % d == 0) return false;
    return true;
}

C++

C++ | square_root.cpp

bool isPrime(int n) {
    if (n < 2) return false;
    for (int d = 2; d <= n / d; ++d)
        if (n % d == 0) return false;
    return true;
}

Analysis: Trial division is O(√n) arithmetic iterations when n is the numeric value, not its bit length.

The C++ version illustrates the same operation. The container, compiler and any functions called by the example still matter when analyzing a complete program.

Space complexity

Representative memory example: A √n-sized buffer.

A buffer allocated with approximately √n elements takes O(√n) extra memory. This is a distinct example from trial division itself, which only needs counters and a temporary remainder, so its auxiliary space is O(1). Counting memory means following how many cells remain simultaneously allocated, not how many values the algorithm examines over its lifetime. For large n, validate conversions and allocation limits before creating the buffer.

The divisor loop and the buffer tell different stories

Trial division keeps the candidate d, the input n and a few temporary arithmetic values, so it uses Θ(1) auxiliary storage. The separate √n-length buffer example deliberately demonstrates a space bound of O(√n): when allocated, its entries remain live at the same time and scale with the chosen limit. A loop that merely visits √n candidates does not need a matching buffer.

On an actual runtime, arrays have headers and allocation limits, so building a buffer of size floor(√n) may fail even though its asymptotic class is correct. The square-root computation must also receive a nonnegative value and produce a safely representable integer size. For a block-decomposition algorithm, maintaining one summary for each block typically uses O(√n) extra cells while storing the original n elements separately.

C#

C# | SquareRoot.cs

int limit = (int)Math.Sqrt(n);
int[] buffer = new int[limit];

C++

C++ | square_root.cpp

#include <vector>
#include <cmath>

int limit = static_cast<int>(std::sqrt(n));
std::vector<int> buffer(limit); // O(sqrt(n)) additional cells

Analysis: Allocating a buffer proportional to √n uses O(√n) auxiliary space; trial division itself uses O(1) extra space.

The stated bound describes stored elements and active call frames. Actual byte counts also depend on runtime, allocator and element representation.

Recognize a square-root algorithm

Look for a stopping boundary of i*i <= n or a carefully overflow-safe equivalent, or for block sizes chosen near √n. Then determine which n the statement means: integer magnitude, number of array elements, or another metric. For trial division, a prime or a number with no tested small factor forces more work than an even composite.

O(√n) time with O(1) auxiliary memory is entirely possible, as the prime check demonstrates. O(√n) auxiliary memory with O(n) preprocessing time is also possible when building block summaries. Do not infer one resource from the other or assume square-root decomposition gives the same result for all supported operations.

Practical example: grouping a large list into blocks

Suppose an array contains 10,000 measurements and you store one summary for every block of 100 measurements. There are about 100 blocks, so the summary array uses roughly √n entries. To answer a range-sum query you can combine summaries for whole blocks and inspect elements in at most two partial blocks. With appropriate block bookkeeping, this yields around O(√n) per query while a full rebuild of summaries still requires O(n) preprocessing.

This is a different use of √n from prime testing: here n counts array elements, not the magnitude of an integer. Changing the problem definition changes what the bound means. Also remember that modifying data can require maintaining the corresponding block summary.

Common mistake

Watch out: Do not equate O(√n) operations on an integer value with O(√b) operations on a b-bit input. Since an integer may have magnitude near 2^b, these are very different claims.

Try it yourself

Compare trial division for prime candidates near 100 and near 10,000. Record the number of divisor tests, not just the elapsed time.

1. Define exactly what n represents.
2. Count the key operation in the best and worst case where relevant.
3. Count the maximum simultaneously live memory.
4. Check your prediction in the Big O explorer.

Continue learning

Big O overview · Time complexity · Space complexity · Compare classes