For nonnegative integer x and positive integer y, initialize the quotient to zero and subtract one divisor at a time:
q := 0; r := x;
WHILE r >= y DO
  r := r-y;
  q := q+1
END
The loop invariant is , , , with x and y unchanged. It is true initially. A body execution changes to and keeps nonnegative because of the guard. The nonnegative integer loop variant strictly decreases by , so termination follows. At exit the guard supplies ; hence
There are exactly body executions. Under the unit-cost model, the time complexity including initialization and the final test is , which is for integer . This is a bound in the value of x, rather than in its encoded bit length.
In binary long division, first double the divisor until it exceeds x, then halve it successively. Keep p = 2^j and d = y*p, so no exponentiation is needed inside a loop:
q := 0; r := x;
j := 0; p := 1; d := y;
WHILE d <= x DO
  d := 2*d;
  p := 2*p;
  j := j+1
END;
WHILE j > 0 DO
  d := d DIV 2;
  p := p DIV 2;
  j := j-1;
  IF r >= d THEN
    r := r-d;
    q := q+p
  END
END
The first loop invariant is , , , and . Every doubling preserves it. For integer inputs, after at most iterations when , d > x; if , this loop has no iterations. The unbounded increase of proves termination. Equivalently, one can use the decreasing nonnegative loop variant while the guard is true.
At the top of the second loop the loop invariant is
It holds on entry because d > x = r. Suppose the old d is and the old p is . After the three halving assignments, and the old remainder satisfies . If , the desired new bound already holds. Otherwise subtracting leaves and adding to q preserves because . The divisions by two are exact: before each halving, j > 0 makes both p and d even.
The loop variant j decreases by one each iteration. At exit , so d = y and the loop invariant gives the required remainder bound. The work per iteration is constant in the unit-cost model, and the two loops have the same number of iterations. For ,
The case , including , takes constant time. These are arithmetic-operation counts with sufficient range for the doubled values; arbitrary-precision arithmetic incurs additional bit complexity. If the inputs were arbitrary positive real numbers, the uniform bound would depend on rather than only ; the stated is the conventional integer division interpretation.
By the time print(n) is called, record has evaluated divisors(i) once for every . In the unit-cost model, the total number of remainder tests is
The record values comparisons add only work, and output is cheap by assumption. The elapsed time is . This measures time to reach a given highly composite number, rather than time as a function of the number of printed records.
Space complexity Created 2026-09-24 Updated 2026-11-05
The space complexity of an algorithm measures the maximum working storage used during its computation as a function of encoded input length. A machine-level definition must state which storage counts. In a common Turing machine convention, a read-only input tape and a write-only output tape are excluded, while visited work-tape cells are counted.
For example, count the ones in a binary string of length by scanning once and retaining a binary counter. Its value ranges from zero to , requiring bits for the counter. Keeping a separate copy of the full input would instead require bits. The computation can therefore use much less working storage than the amount of data it examines.
The maximum concerns simultaneously retained storage, not the total amount allocated and later reused over time. Bit complexity and a unit-cost model also need care here: treating an arbitrarily large integer as one storage cell can hide its growing representation size.