Suggest an edit

Improve this article

Refine the answer for “What properties should an algorithm have?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

1. Finiteness: the algorithm must terminate in a finite number of steps.
2. Definiteness (unambiguity): each instruction is formulated unambiguously; there is no ambiguity at any step.
3. Discreteness: the process consists of separate, clearly delimited steps.
4. Generality (mass character): the algorithm is applicable to an entire class of input data, not to a single example.
5. Effectiveness and correctness: for valid inputs, a result satisfying the specification is obtained.
6. Efficiency: reasonable time and memory costs; an assessable computational complexity.

## Detailed answer

Below are the key properties of an algorithm, why they are needed in practice, and how to recognize them in examples.

### 1) Finiteness (termination)

The algorithm must be guaranteed to terminate in a finite number of steps for any valid input data. Otherwise it is an infinite process, not an algorithm.

- Check: is there an invariant and a decreasing measure that strictly shrinks on every loop and reaches the base case?
- Sign of a problem: a loop/recursion without an exit condition that is guaranteed to become true.

```
// Example of a finiteness violation:
function loopForever() {
  while (true) {
    // no decreasing measure and no exit condition
  }
}
```

### 2) Definiteness (unambiguity of instructions)

Every step must be described unambiguously: the executor (the computer) must not need to interpret the meaning. This rules out ambiguous terms like "process", "simplify", "significantly reduce" without a strict definition.

```
// Bad (ambiguous):
// "Perform input processing"
// Not clear: what exactly, and how?

// Good (unambiguous):
function normalize(input) {
  // 1) trim whitespace at the edges
  // 2) convert to lowercase
  // 3) collapse sequences of whitespace into one space
  return input.trim().toLowerCase().replace(/\s+/g, ' ');
}
```

### 3) Discreteness

The algorithm must consist of a sequence of elementary steps, each of which is executable and has an observable effect. This allows correctness and complexity to be analyzed step by step.

```
// Discrete steps of selection sort (described explicitly):
function selectionSort(a) {
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {             // step: choose position i
    let min = i;                                 // step: assume the minimum
    for (let j = i + 1; j < n; j++) {            // step: search for the minimum in the tail
      if (a[j] < a[min]) min = j;                // step: update the minimum
    }
    if (min !== i) [a[i], a[min]] = [a[min], a[i]]; // step: swap
  }
  return a;
}
```

### 4) Generality (mass character)

The algorithm must be applicable to an entire family of inputs described by the domain. The specification fixes the requirements on the input (preconditions) and the shape of the result (postcondition).

```
// Binary search works for any sorted array of comparable elements
// (precondition: the array is sorted in non-decreasing order)
function binarySearch(arr, x) {
  let l = 0, r = arr.length - 1;
  while (l <= r) {
    const m = l + ((r - l) >> 1);
    if (arr[m] === x) return m;      // postcondition: index of the found element
    if (arr[m] < x) l = m + 1; else r = m - 1;
  }
  return -1;                         // if the element is absent
}
```

### 5) Effectiveness and correctness

Effectiveness: the algorithm always produces some result for valid inputs. Correctness: that result satisfies the specification (postconditions). Provability of correctness is the most important requirement for algorithms used in production.

```
// Specification (in words):
// Input: non-negative integers a, b, not both zero.
// Output: gcd(a, b) - the greatest common divisor, i.e. d | a, d | b, and
// for any d' | a and d' | b it holds that d' <= d.

function gcd(a, b) {
  while (b !== 0) {
    const t = a % b;
    a = b;
    b = t;
  }
  return Math.abs(a);
}

// Correctness sketch:
// - Invariant: gcd(a, b) does not change when replacing (a, b) := (b, a mod b).
// - Termination: b decreases modulo and reaches 0 in a finite number of steps.
// - Postcondition: when b = 0, the answer a is the sought GCD.
```

### 6) Efficiency (time and memory complexity)

The algorithm must solve the problem with acceptable costs. Efficiency is expressed asymptotically (Big-O notation) and empirically (benchmarks). In an interview, it is important to be able to discuss time and space complexity, as well as possible optimizations.

- Time: how many elementary operations are performed (for example, O(n log n)).
- Memory: additional memory used (for example, O(1) for Euclid's algorithm).
- Trade-offs: time ↔ memory, accuracy ↔ speed, and so on.

```
// Naive GCD (inefficient): O(min(a,b))
function gcdNaive(a, b) {
  let d = Math.min(a, b);
  while (d > 0) {
    if (a % d === 0 && b % d === 0) return d;
    d--;
  }
}

// Euclid's algorithm is more efficient: O(log min(a,b)) steps.
```

## Related concepts that are often asked about

- Inputs/outputs: a clear definition of the data format and contracts (pre- and postconditions).
- Determinism vs non-determinism: an algorithm can be non-deterministic, but its specification and correctness must still be defined (for example, any valid result from a set).
- Provability: loop invariants, recursive base cases, decreasing measure, partial/total correctness.

## Bottom line (for an interview answer)

An algorithm is a finite, discrete, and unambiguous sequence of steps, applicable to an entire class of inputs (generality), which for valid data guarantees a correct result and does so efficiently in time and memory.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts923 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.