What does "discreteness" of an algorithm mean?

AlgorithmsJunior~3 min read

Short answer

Discreteness of an algorithm is the property of solving a problem through a sequence of separate, indivisible steps (iterations), where each state and action is described by a finite set of symbols, and changes happen abruptly, step by step, rather than continuously.

Detailed answer

In computer science, an algorithm is discrete by definition: it executes in steps, changing the state of the system at distinct, distinguishable moments in time. This makes it possible to formally describe, analyze, and implement algorithms on digital machines.

Key aspects of discreteness

Stepwise execution: the algorithm executes as a sequence of atomic steps, each of which transitions the system from state S to S′.
Atomicity of operations: basic actions are considered indivisible and are executed as a whole (comparing two values, assignment, accessing an array element, and so on).
Discrete representations: the input data, internal states, and output are encoded as finite strings of symbols (bits, numbers with a finite bit width, and so on).
Discrete "time": there is no infinite number of intermediate states between steps; the step index is an integer k = 0, 1, 2, ….

Why this matters

Implementability: digital computers are themselves discrete, so algorithms built from a finite set of steps and symbols can be implemented and executed.
Formal verifiability: the presence of separate steps and states allows correctness to be proven (invariants, partial/total correctness) and complexity and resources to be analyzed.
Testability and reproducibility: discrete steps make it easier to reproduce scenarios, debug, and measure.

Relation to continuous problems

Algorithms often solve problems from continuous domains (for example, optimization over real numbers, integrating differential equations). At the same time, the algorithms themselves remain discrete: they take finite measurements, make a finite number of steps, and produce a result of finite precision. The transition from a continuous formulation to a discrete procedure is called discretization.

What discreteness is not

Not about determinism: an algorithm can be discrete and at the same time probabilistic or non-deterministic - what matters is the stepwise nature, not the predictability of the result.
Not a guarantee of termination: discreteness does not mean the algorithm will necessarily terminate; the termination property is considered separately.
Does not require a discrete domain: even with real numbers, an algorithm operates with finite precision (floating point), performing discrete steps.

Intuitive, semi-formal description

Let S₀ be the initial state, S₁, S₂, … the states after applying the rules. An algorithm is a transition relation → such that at each step one (or a finite number of) atomic transitions Sₖ → Sₖ₊₁ is performed. Steps are indexed by integers k - this is exactly what discreteness is.

Example 1: binary search (strictly discrete)

The algorithm performs a sequence of comparisons/halvings; each comparison is an atomic step.

function binarySearch(arr, x) {
  let l = 0, r = arr.length - 1;
  while (l <= r) {
    const m = (l + r) >> 1; // discrete choice of the middle
    if (arr[m] === x) return m;           // atomic check
    if (arr[m] < x) l = m + 1; else r = m - 1; // discrete state transition
  }
  return -1; // not found
}

Each iteration is one discrete step; the number of steps is proportional to O(log n).

Example 2: discretizing a continuous problem (Euler's method)

We solve the differential equation y′ = f(t, y) with step h. Although the problem itself is continuous, the procedure is discrete: we change t in jumps of h and perform finite computations at each step.

function euler(f, y0, t0, t1, h) {
  const points = [[t0, y0]];
  for (let t = t0; t < t1; t += h) {
    y0 = y0 + h * f(t, y0); // discrete state update
    points.push([t + h, y0]);
  }
  return points;
}

// Example: y' = y, y(0) = 1, we expect exp(t)
const approx = euler((t, y) => y, 1, 0, 1, 0.1);
console.log(approx);

Decreasing h increases precision, but the algorithm remains discrete: it performs finite, atomic steps.

Counterexample (not discrete)

"Turn the knob by exactly π/10 of a turn with infinite precision" is a requirement on a continuous physical process with infinite measurement precision. Such a process cannot be represented as a finite sequence of atomic steps with finite-precision state encoding, so it is not an algorithm in the strict discrete sense.

Summary

Discreteness is a fundamental property of algorithms that lets us formally describe, analyze, and implement them: algorithms work with finite descriptions of states and solve problems step by step. Even for continuous problems, we use discrete procedures (discretization) and produce answers of finite precision.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.