Suggest an edit

Improve this article

Refine the answer for “What is a linear algorithm?”. 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

A linear algorithm is either a sequential algorithm without branching or loops (each step executes once, strictly top to bottom), or an algorithm with linear time complexity O(n), where the running time grows proportionally to the size of the input data. In conversation, it is important to clarify which sense is meant: the execution structure or the complexity.

## Detailed answer

### Definition and context

- Linear by structure: a sequence of steps with no conditions (if/switch) and no loops (for/while). The execution path is the same for any input.
- Linear in time (O(n)): the running time grows linearly with the input size. Such an algorithm may contain loops or recursion, but each element of the input is processed a fixed number of times.

### Implementation examples

#### 1) Linear by structure (no branching or loops)

A simple JavaScript example: computing the area and perimeter of a rectangle from its given sides.

```javascript
const a = 5; // side A
const b = 3; // side B

const area = a * b;
const perimeter = 2 * (a + b);

console.log('Area:', area);
console.log('Perimeter:', perimeter);

// No conditions and no loops - execution runs strictly top to bottom.
```

#### 2) Linear in time O(n)

Summing the elements of an array is a linear time complexity: each element is visited once.

```javascript
function sum(arr) {
  let s = 0;
  for (const x of arr) {
    s += x; // every element is processed exactly once
  }
  return s;
}

console.log(sum([1, 2, 3, 4])); // 10
```

There is a loop here, so by structure this is not a linear algorithm, but in time it is linear (O(n)).

### How to tell them apart in an interview

- If it is about structure: no branching and no loops - this is linear by structure.
- If it is about complexity: we estimate how time/memory depends on n. A single pass over the data - O(n) - is linear in time.
- Clarify the term: "linear by structure, or linear complexity (O(n))?"

### Typical mistakes and questions

- Confusing a "linear algorithm" as a sequence of steps with "linear complexity" O(n).
- Assuming a loop always means non-linear complexity. A loop can be either linear or quadratic - it depends on the number of nestings and repetitions.
- Ignoring memory: there are algorithms that are linear in time but not in memory (for example, ones that create an array of size n).

### Comparison with other classes (by time)

- O(1) - constant: an example is accessing an array element by index.
- O(log n) - logarithmic: binary search over a sorted array.
- O(n log n) - typical for efficient sorts (merge/quick on average).
- O(n^2) - quadratic: nested loops over the same set of data.

### When to use it

- A linear structure - when the algorithm needs to be as simple and predictable as possible (execution as a fixed chain of actions).
- Linear complexity - when scalable processing of large input data in a single pass is needed (streaming/iterative processing).

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

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.