What does O(n) - linear complexity - mean?

AlgorithmsJunior~3 min read

Short answer

O(n) is linear complexity: the running time (or the number of elementary operations) grows proportionally to the input size n. If you double n, the time roughly doubles too. This usually corresponds to a single full pass over the data with no nested loops that depend on n.

In detail

What "linear" means

Linear complexity is described by a function of the form a·n + b: the constants a and b are dropped in O(·) notation, giving O(n). Intuitively: each added element adds roughly the same amount of work, and a full pass over an array of length n takes n steps in total.

A single loop over the data with no nested operations depending on n - O(n).
Several independent passes: O(n) + O(n) = O(n).
An early exit is possible, but the classic estimate is for the worst case: it is still O(n).
If there is a nested loop but it runs a constant number of times, the complexity remains O(n).
For two different inputs n and m: they add up - O(n + m).

Examples of O(n) algorithms

Linear search in an unsorted array (worst case - scanning all elements).

js
function linearSearch(arr, target) { for (let i = 0; i < arr.length; i++) { if (arr[i] === target) return i; // early exit - best case O(1) } return -1; // worst case - O(n) }
Summing the elements of an array.

js
function sum(arr) { let s = 0; for (const x of arr) s += x; // a single pass return s; // O(n) }
Finding the maximum.

js
function max(arr) { if (arr.length === 0) return undefined; let m = arr[0]; for (let i = 1; i < arr.length; i++) { if (arr[i] > m) m = arr[i]; } return m; // O(n) }
Counting unique values with a Set - O(n) time, O(n) memory.

js
function uniqueCount(arr) { const set = new Set(); for (const x of arr) set.add(x); return set.size; // Time: O(n), Memory: O(n) }

Several passes - still O(n)

Two sequential linear passes add up and remain linear.

function twoPasses(arr) {
  for (const x of arr) {/* ... */} // O(n)
  for (const x of arr) {/* ... */} // O(n)
  // Total: O(n + n) = O(n)
}

A nested loop with a constant - also O(n)

for (const x of arr) {
  for (let k = 0; k < 10; k++) {
    // 10 is a constant, it does not depend on n
  }
}
// Complexity: 10 * n => O(n)

Two different inputs - O(n + m)

function merge(a, b) {
  const res = [];
  for (const x of a) res.push(x); // O(n)
  for (const y of b) res.push(y); // O(m)
  return res; // O(n + m)
}

Complexities side by side for comparison

O(1) - constant: the time does not depend on n.
O(log n) - logarithmic: each step shrinks the problem by a factor (binary search).
O(n log n) - for example, efficient sorts (MergeSort, QuickSort on average).
O(n^2) - nested loops over n (comparing every pair of elements).

How to quickly estimate linearity

Define the input size n (number of elements, string length, and so on).
Count how many times you touch each element - no more than a constant number of times? Then it is most likely O(n).
Add up the independent parts and drop the constants: O(n) + O(n/2) + O(100) → O(n).
Account for the cases: best/average/worst. Linear search: best - O(1), worst - O(n).
Check the memory: if you store a structure that grows proportionally to n, then it is O(n) in memory too.

Typical traps

A nested loop does not always give O(n^2): if the inner one is bounded by a constant, the total is O(n).
Copying operations inside a loop can turn linearity into quadratic behavior.

js
function badAppend(items) { let res = []; for (const x of items) { res = [...res, x]; // copies the whole res every time → O(len) } return res; // O(n^2) total } function goodAppend(items) { const res = []; for (const x of items) res.push(x); // amortized O(1) return res; // O(n) total }
Two consecutive map/filter calls - still O(n). Merging them into a single pass reduces the constants but does not change the O-notation.
An early exit improves the best/average case, but the worst-case asymptotics remains O(n).

Intuition: double the amount of data, and the time roughly doubles. That is linearity.

Short Answer

Interview ready

Premium

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