What is a linear algorithm?

AlgorithmsJunior~2 min read

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).

Short Answer

Interview ready

Premium

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