Arithmetic complexity 2026-11-05
Arithmetic complexity counts arithmetic operations under an explicitly stated computational model. One may count additions, subtractions, multiplications and divisions over a specified field as unit operations, or distinguish their costs. This exposes algebraic structure without yet accounting for how each number is represented.
For a degree- polynomial , Horner's method sets and for . It returns using multiplications and additions. Repeatedly expanding each power independently would obscure this reuse of earlier work. An arithmetic circuit represents such dependencies as a finite network of arithmetic operations.
Bit complexity asks an additional question: how much work is required to perform those operations on the encoded numbers? Multiplying two large integers is one arithmetic operation but requires processing their bits. Intermediate numerators and denominators can also grow. Conversely, a small arithmetic-operation count does not bound round-off error; the numerical stability of an evaluation scheme is a separate property.
Bit complexity Created 2026-10-31 Updated 2026-11-05
The number of elementary operations on bits required by an algorithm. Arithmetic-operation counts treat operations on entire integers as units, whereas bit complexity charges for the sizes of their operands. An algorithm using few multiplications can therefore require substantially more bit operations when the operands grow. State the model when comparing bounds for repeated squaring or dynamic programming counts.
Computational complexity theory Created 2026-09-24 Updated 2026-11-05
Computational complexity theory studies the resources required to solve families of computational problems. A statement specifies an input encoding and a model of computation, then measures resources such as running time, computer memory or query complexity as the encoded input length grows. An algorithm's upper bound describes one method; a problem lower bound constrains every permitted algorithm in the stated model.
For decision problems, a complexity class collects problems with a shared resource guarantee. P uses deterministic polynomial time; NP permits polynomially bounded witnesses checked in polynomial time. The distinction separates finding an answer from verifying a supplied certificate.[ref]
The cost model is part of the mathematics. Bit complexity charges for arithmetic on operands of growing size, while a comparison model counts comparisons of keys. A polynomial-time algorithm also need not be practical at every scale: its exponent and constants still affect actual running time. These distinctions make complexity bounds useful for comparing both mathematical possibilities and concrete implementations.
Integer logarithm 2026-10-31
For integers and , the integer logarithm is the largest nonnegative integer such that . Equivalently,
The equivalence follows from the monotonicity of exponentiation in its exponent and the definition of the floor function. For example, , so the base-three integer logarithm of is .
A multiplication loop maintains and accepts another factor while . Repeated squaring makes the search faster: precompute starting at , and consider these factors in decreasing . Include a factor when the accumulated product remains at most . If , the loop invariant before considering is . Accepting exactly when halves that uncertainty, proving the greedy algorithm returns . This takes arithmetic operations; it is not the same claim as this bound on bit complexity.
For positive operands in bounded integer arithmetic, test before multiplying by . Integer division makes this equivalent to while preventing integer overflow in a rejected candidate.
Lattice algorithm 2026-11-05
In the geometry of numbers, a lattice algorithm works with a Euclidean lattice, usually specified by linearly independent vectors whose integer linear combinations form
The basis of a Euclidean lattice is not unique. For example, and generate the same Euclidean lattice as and : replace the second vector by itself minus 100 times the first. This integer linear combination is reversible, so it changes the representation without changing the set of Euclidean lattice points.
Lattice reduction seeks a more useful basis of a Euclidean lattice, with shorter and less nearly dependent vectors. The Lenstra-Lenstra-Lovász lattice basis reduction algorithm combines integer basis changes with Gram-Schmidt orthogonalization and comparisons controlling the quality of the result. It is a polynomial-time example, but it does not generally return an exactly shortest vector.[ref] Better bases make geometric searches and lattice-based cryptography analysis more practical. The geometry and the sizes of the integer coordinates both matter: a small number of arithmetic steps need not imply a small bit complexity.
Model of computation 2026-11-05
A model of computation specifies how inputs are represented, which states and operations are available, how execution proceeds and what counts as its output and resource cost. Examples include Turing machines, random-access machines, Boolean circuits and the lambda calculus. A mathematical algorithmic claim is interpreted within such a model, even when the model is left implicit.
For example, adding two integers is one instruction in a unit-cost machine model. In a bit-cost model, operating on arbitrarily long integers requires time depending on their encoded lengths. A bound counting arithmetic operations therefore need not be a bound on bit complexity. Likewise, a circuit family can supply separate hardware for each input length, while a uniformity requirement asks one algorithm to generate those circuits. Stating the model makes efficiency comparisons meaningful and separates questions of computability from the cost of a chosen representation.
Set . Independently sample an edge coloring exactly as in part (d), count its monochromatic copies of by examining all four-vertex subsets, and accept precisely when . Otherwise start over with a fresh edge coloring.
To prove an expected polynomial time bound, the existence argument alone is insufficient: we need a lower bound on the acceptance probability at this exact threshold. Since is a nonnegative integer with expectation , rejection implies . Markov's inequality therefore gives the integer-valued expectation threshold restart bound
The number of attempts has a geometric distribution, with expectation at most . Sampling the edge coloring costs random bits, and checking all four-vertex subsets costs operations, since only six edges must be tested per subset. Hence
This is a randomized algorithm that always returns an edge coloring meeting the original threshold and terminates with probability one. The stated operation count uses -bit counters; counting their bit complexity explicitly introduces at most a further logarithm factor and still gives polynomial time. For , return any edge coloring immediately.
Order the edges arbitrarily and fix their colours one at a time. After a partial assignment , regard all unassigned edges as independent fair red/blue choices, and compute
The conditional expectation of a monochromatic clique count is easy to compute. For each four-vertex subset , let be the number of its six edges still unassigned. Its contribution to is
In the second case, every remaining edge must match the already fixed colour; this includes a completely fixed monochromatic copy, for which and the contribution is one. In the last case, the six unassigned edges may become either all red or all blue. By linearity of expectation,
For the next unassigned edge , compute and . The law of total expectation gives
Choose the colour with the smaller value, resolving a tie by a fixed rule. At least one is at most their average, so the loop invariant is that never increases. Initially ; once every edge is fixed, there is no randomness left and . Therefore the method of conditional expectations guarantees
A direct implementation recomputes both sums over all four-vertex subsets for each of the edges, requiring arithmetic operations. The comparisons can be exact: every contribution is a multiple of , so store as an integer with bits. This gives bit complexity with elementary arithmetic, and hence a deterministic polynomial time construction. No random sampling is performed by this derandomization.
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.
Store a second array weight with weight[k] = 2^k. Descending through the binary digits of the answer gives this greedy algorithm:
PROCEDURE FastLog(b, n: INTEGER): INTEGER;
VAR b2, weight: ARRAY enough OF INTEGER;
    top, k, i, p: INTEGER;
BEGIN
  b2[0] := b; weight[0] := 1; top := 0;
  WHILE b2[top]*b2[top] <= n DO
    b2[top+1] := b2[top]*b2[top];
    weight[top+1] := weight[top]+weight[top];
    top := top+1
  END;
  i := 0; p := 1; k := top;
  WHILE k >= 0 DO
    IF p*b2[k] <= n THEN
      p := p*b2[k]; i := i+weight[k]
    END;
    k := k-1
  END;
  RETURN i
END FastLog;
For the second loop, write . Immediately before processing , its loop invariant is
Initially the failed squaring guard gives ; this also holds when , since then . The test succeeds exactly when . If successful, adding selects that binary digit; otherwise the upper bound tightens to . Either way the invariant holds for the next smaller . At , , so i = L.
There are squarings and descending tests. For fixed , this is arithmetic operations, hence logarithmic in the bit length of , and also within the weaker bound. This counts arithmetic operations on integers as unit cost; bit complexity would also charge for the growing operands. No division is used.
Use dynamic programming in increasing order of the maximum permitted part and then of the remaining sum. Let Count be a sufficiently wide integer type and let table have dimensions (MaxN+1) by (MaxN+1):
PROCEDURE CountPartitions(n: INTEGER): Count;
VAR i, j: INTEGER;
    table: ARRAY MaxN+1, MaxN+1 OF Count;
BEGIN
  table[0,0] := 1; j := 1;
  WHILE j <= n DO table[0,j] := 0; j := j+1 END;
  i := 1;
  WHILE i <= n DO
    table[i,0] := 1; j := 1;
    WHILE j <= n DO
      table[i,j] := table[i-1,j];
      IF j >= i THEN
        table[i,j] := table[i,j] + table[i,j-i]
      END;
      j := j+1
    END;
    i := i+1
  END;
  RETURN table[n,n]
END CountPartitions;
Require . The outer loop invariant says all rows below equal . The inner loop invariant additionally says entries before column in the current row are correct. Its dependencies are the previous row and the earlier column , so no future entry is read. Each state is evaluated once, giving arithmetic operations and stored counts. A memoization table around part (a)'s recursion is another valid way to share states; its entries need a separate “computed” flag because zero is a legitimate answer. Growing count sizes affect bit complexity and can cause integer overflow in a fixed-width Count.
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.
Unit-cost model 2026-10-31
A computation-cost convention assigning constant cost to specified primitive operations. For exact unbounded integer arithmetic this can differ substantially from bit complexity: a multiplication of increasingly large values is one primitive operation but requires more bit operations. State which convention is used when estimating an algorithm's running time.