Suggest an edit

Improve this article

Refine the answer for “What does O(n) - linear complexity - mean?”. 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

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.

```js
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)

```js
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)

```js
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

1. Define the input size n (number of elements, string length, and so on).
2. Count how many times you touch each element - no more than a constant number of times? Then it is most likely O(n).
3. Add up the independent parts and drop the constants: O(n) + O(n/2) + O(100) → O(n).
4. Account for the cases: best/average/worst. Linear search: best - O(1), worst - O(n).
5. 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.

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

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.